Extract Evenly Divisible using recursive function

Question

I am trying following program but I have done without sorting so someone would please help me that how to sort return output?

Given a array of numbers, and a single number n, return an extracted array of unique numbers that are evenly divisible by n. Your extracted array should be sorted in ascending numerical order. Examples: If you ran extractEvenlyDivisible([1,2,3,4,5,6,7,8,9], 3) you would get a return value of [3,6,9]. If you ran extractEvenlyDivisible([1,9,3,4,3,6,7,8,9], 3) you would get a return value of [3,6,9].

When giving by sort array then output coming sorted(3,6,9)::

var numbers = [1,2,3,4,5,6,7,8,9];
even_func(numbers,3);
function even_func(arr,n,i=0){
    if(arr[i] == undefined) return ;
    
    if(arr[i] % n == 0){
            console.log(arr[i]);
            var t  = arr.filter(x => {
              return x != arr[i];
            });
            arr = t; i=0;
    }
    even_func(arr, n,  i+1);   
}

But when giving unsorted array then output comes unsorted(9,3,6) so how to sort output like 3,6,9 without using global variables.

var numbers = [1,9,3,4,3,6,7,8,9];
    even_func(numbers,3);
    function even_func(arr,n,i=0){
        if(arr[i] == undefined) return ;
        
        if(arr[i] % n == 0){
                console.log(arr[i]);
                var t  = arr.filter(x => {
                  return x != arr[i];
                });
                arr = t; i=0;
        }
        even_func(arr, n,  i+1);   
    }

Answer 1

With JavaScript Array Functions

A simple approach is to use a Set to filter out duplicates, then transform the Set back to an array so you can filter out the ones that can be divided by n without an remainder. Then sort the values using sort().

function evenNumber(array, divideBy){
    const set = new Set(array);
    const filtered = [...set].filter(number => number % divideBy === 0);
    return filtered.sort((a, b) => a - b);
}

console.log(evenNumber([1,2,3,4,5,6,7,8,9], 3));
console.log(evenNumber([1,9,3,4,3,6,7,8,9], 3));

Without using built-ins

As you said you don't want to use built-in functions in the comments here a solution without them following a different approach.

It would of course also be possible to use the same approach as above using JS objects instead of a Set or by implementing an own version of Set and some sorting algorithm but I think that does not really make sense because you would just re-implement built-ins that are already implemented (and tested!) so I am following another approach here.

In this approach I keep an array sorted that is always sorted and will gradually be filled with values. First I loop over all values and check whether a value divides the given divider without leaving a remainder. If it does not, we can move on to the next element. If it does I need to check if we already have that in sorted array. Because it's sorted I can use binary search to do that and will be able to (not) find the value in O(log n). I also remember the position computed by binary search where a value is found or if it's not in the array yet, the position where it would need to go. Then if the value is already in the sorted array it can be ignored. If not, we have a new value to insert in the array. Thanks to the binary search we already know the position we need to put the new value.

/**
 *
 * @param {Array<number>} array array to search
 * @param {number} value value to search for
 * @returns object containing boolean "found" and the position of the element; or if not found the position the value would need to be placed in in the array
 */
function binarySearch(array, value) {
  let left = 0;
  let right = array.length - 1;
  let lastLocation = 0;
  while (left <= right) {
    const middle = (right + left) >> 1;
    if (array[middle] === value)
      return {
        found: true,
        location: middle,
      };
    else if (array[middle] > value) {
      right = middle - 1;
      lastLocation = right;
    } else {
      left = middle + 1;
      lastLocation = left;
    }
  }
  return {
    found: false,
    location: Math.min(array.length, lastLocation + 1),
  };
}

/**
 *
 * @param {Array<number>} array array of numbers
 * @param {number} divideBy number which is used to divide each value by
 */
function evenNumber(array, divideBy) {
  // array that will always be sorted as we insert new values
  const sorted = new Array();
  // loop over all elements within the array
  for (let i = 0; i < array.length; i++) {
    const element = array[i];
    if (element % divideBy !== 0) continue;
    // search for the element in the array in O(log n)
    const result = binarySearch(sorted, element);
    // the value is already in the array => skip
    if (result.found) continue;
    // we have a new value to insert in the array
    // thanks to the binary search we already know the position we need to insert the element
    insertValue(sorted, element, result.location);
    
  }
  return sorted;
}

function insertValue(array, newElement, position) {
  if (position > array.length) position = array.length;
  else if (position < 0) position = 0;
  
  if (position < array.length) {
    // element is supposed to go to a spot where we already have a value (assuming a continious array)
    // increase array length by one and shift all values by 1 to the right so we get an empty spot at position
    array.length++;
    for (let i = array.length - 1; i > position; i--) {
      array[i] = array[i - 1];
    }
  }
  // set element at the position it is supposed to be in
  array[position] = newElement;
  return array;
}

console.log(evenNumber([1, 2, 3, 4, 5, 6, 7, 8, 9], 3));
console.log(evenNumber([1, 9, 3, 4, 3, 6, 7, 8, 9], 3));
console.log(evenNumber([1, 9, 2, 12, 12, 16, 7, 8, 9, 5], 3));

insertValue(array, newElement, position) is the equivalent to sorted.splice(result.position, 0, element), so I would normally use this, because there's no point in just re-implementing built-in methods and it's also not a very safe way to operate.

You might wanna have a look at this blog post which give you a bit of background on some of the array operations I am doing.