Array Addition I JavaScript function on Coderbyte

Question

I am doing a challenge on Coderbyte and I would be grateful for any advice on my question:

The challenge given to me: "Using the JavaScript language, have the function ArrayAdditionI(arr) take the array of numbers stored in arr and return the string true if any combination of numbers in the array can be added up to equal the largest number in the array, otherwise return the string false. For example: if arr contains [4, 6, 23, 10, 1, 3] the output should return true because 4 + 6 + 10 + 3 = 23. The array will not be empty, will not contain all the same elements, and may contain negative numbers. "

The way I attempted to solve it: http://jsfiddle.net/reLsg0fg/

function ArrayAdditionI(arr){
  var newArr=arr.sort(); // sorted from smallest to largest.
  var largestNum=newArr.slice(-1); // Gets the last number, which would be the largest.
  var loopArr=arr.sort().pop(); // Takes out the largest number for adding later.
  var result=0;

  for(var i=0; i<loopArr.length; i++){ // loops through all numbers.
    if(result/largestNum !== 1){ //when you divide a number by itself it will be 1.
        result+=loopArr[i]; // keep adding each number until get largest number.
    }else if(result === largestNum){
    return true;
    }
  } 
  return false;
}


// TESTS    
console.log("-----");   
console.log(ArrayAdditionI([4,6,23,10,1,3]));    
console.log(ArrayAdditionI([5,7,16,1,2]));   
console.log(ArrayAdditionI([3,5,-1,8,12]));   

I'm supposed to get true, false, true. But I get false, false, false as if something is wrong within my loop. JSFiddle: http://jsfiddle.net/reLsg0fg/

I would appreciate any suggestions. Thank you ^^

Answer 1

Sort Array using

arr.sort(function (a, b) { return a - b })

Answer 2

I have tried to solve this problem with a for loop but I missed the fact that the challenge is not asking that all numbers need to add up to equal the largest num, but it is also possible to add up to the largest num if we take some numbers out. Thus I decided to solve with recursion.

Tips:
* The Math.max.apply() method takes an array and returns the largest number. Note that it usually works on strings as Math.max().
* the sort() method can take a parameter to further expand it's purpose. Usually it only sorts strings, but to sort numbers we include a function that finds which number is bigger.
* First get the largest number.
* Sort the array and remove the largest number to be used for recursion later.
* Create a recursion function that checks if the numbers add up to the largest number, and if not, check that if some numbers in array are subtracted from the largest num they are equal to the largest number.

function ArrayAdditionI(array){
  var largestNum = Math.max.apply(0, array); // gets the largest number in array.
  array.sort(function(a,b){ return a-b;}).pop(); // sorts array and removes last(largest) number.

  function recursionCheck(arr, sum){
  // the base case when array empty.
    if(arr.length === 0){ 
    return sum === 0;
    }

    var arrBeginNum=arr[0];  

    // for every recursion take away one number(the first one in this case).
    arr = arr.slice(1);

    // first check if numbers sum up to largest num if not, check if removing numbers adds up to largest num.
    return recursionCheck(arr, sum) || recursionCheck(arr, sum - arrBeginNum);
  }

 // recursion needs to be called for it to start.
return recursionCheck(array, largestNum);
   }

// TESTS
console.log("-----");
console.log(ArrayAdditionI([1,2,3,5,4])); ==> true
console.log(ArrayAdditionI([21,10,12,9,2])); ==> true
console.log(ArrayAdditionI([4,6,23,10,1,3])); ===> true
console.log(ArrayAdditionI([5,7,16,1,2])); ===> false
console.log(ArrayAdditionI([3,5,-1,8,12])); ===> true

Answer 3

This might not be the complete solution yet, but here are the JavaScript-Problems:

largestNum was an array in you algorithm .sort() was not working

function ArrayAdditionI(arr){
    var largestNum = Math.max.apply(0, arr); // Gets the last number, which would be the largest.
    arr.sort(function(a, b){return a-b})
    arr.pop(); // Takes out the largest number for adding later.
    var result=0;  

Also use if(result !== largestNum) {, Division is expensive and might have unexpected results with floating-point numbers.

Thats it for your JavaScript. But I am pretty sure the Algorithm is wrong - but I think this is up to you

Note that the example [4, 6, 23, 10, 1, 3] => 4 + 6 + 10 + 3 = 23 is not just adding up the lowest to the biggest value to try and match it.

Answer 4

A possible example of a solution for the problem.

How this works:

• First sort all items descending
• Shift the first element to largest
• Call the recursive function y with the reduced array, the largest value and a variable which holds an empty array for the successfully added items.

The recursive function works basically in two parts

1. Test if the remaining sum is zero, if so the result is achieved and return true, which finished the function.
2. If not iterate through the array and
   • Make a copy from the array
   • Get the value from the position with splice
   • Test, if the value is smaller or equal the remaining sum and the result of the call of y with the shorted array, sum minus value and a new array with the used items and the acual item.
   • If true return true and finish the function.
3. If not finished before return false.

function x(array) {

    function y(a, s, result) {
        var aa, i, v;
        if (s === 0) {
            document.write('<pre>result: ' + JSON.stringify(result, 0, 4) + '</pre>');
            return true;
        }
        for (i = 0; i < a.length; i++) {
            aa = a.slice();
            v = aa.splice(i, 1)[0];
            if (v <= s && y(aa, s - v, result.concat(v))) {
                return true;
            }
        }
        return false;
    }

    var largest,
        r = [];
    array.sort(function (a, b) { return b - a; });
    largest = array.shift();
    document.write('largest value: ' + largest + '<br>');
    return y(array, largest, r);
}

document.write(x([4, 6, 23, 10, 1, 3]) + '<hr>');
document.write(x([5, 7, 16, 1, 2]) + '<hr>');
document.write(x([3, 5, -1, 8, 12]));

Answer 5

Thanks @mar Here is a version in Kotlin if someone needs

private fun returnResult(arr: Array<Int>): Boolean {
    arr.sort()
    val largestNumber = arr.last()
    val arrWithoutLargest = arr.dropLast(1).toTypedArray()
    return recursionCheck(arrWithoutLargest, largestNumber)
}

private fun recursionCheck(arr: Array<Int>, sum:Int): Boolean {
    if (arr.isEmpty()) return sum == 0

    val arrBeginNum = arr[0]

    val arr2 = arr.drop(1).toTypedArray()

    return recursionCheck(arr2, sum) || recursionCheck(arr2, sum - arrBeginNum)
}