Coderbyte

So I've been reading up on a lot of websites from people who were preparing for the Hack Reactor interview that this was the hardest question. I thought this was going to take me hours, but somehow I managed to get this code to pass all the tests within 5 minutes, so I'm thinking there's no way that my code is perfect. Basically, my approach was to store the largest value if a separate variable. Then I added up the rest of the variables left in the original array and left it in a variable called sum. Then I went backwards through the array, where if the sum minus any number equaled the largest number, then true would be returned. Same if the largest value minus the sum equaled 0 (in which case all the numbers that were left over exactly equaled the largest number). Is this truly a "right" solution, or did I get lucky? Because it seemed simple enough to me...I was not expecting to pass so quickly.

function ArrayAdditionI(arr) { 

  arr = arr.sort(function(a,b){return a-b;});
  var largestval = arr.pop();
  var sum = arr.reduce(function(x,y){return x +y;});

  for (var i = arr.length-1; i>=0; i--){
    if (sum-arr[i]==largestval){
      return true;
  }
    if (largestval-sum == 0){
      return true;
    }
  }
  return false;
}

// keep this function call here 
// to see how to enter arguments in JavaScript scroll down
ArrayAdditionI(readline());

I agree with you, this problem is tough!! It was the hardest of the "Easy" set for me. Here's a simpler solution, using recursion, than what the others suggested. It's based on a very similar example from Chapter 3 of Eloquent Javascript < eloquentjavascript.net/03_functions.html#p_IWOXsklZbt >:

function ArrayAdditionI(arr) { 
  
  // sort array ascending
  arr = arr.sort( function(a,b){return a - b});
  
  var max = arr.pop();
  
  function lookForSolution(){
    function search(sum,i) {
      if ( sum == max ) {
        return true;
      }
      else if ( sum > max || i == arr.length ) {
        return null;
      }
      else {
        return search(sum + arr[i],i + 1) ||
               search(sum,i + 1);
      }
    }
    
    // start search with sum of zero in position zero:
    return search(0,0);
  }
  
  return lookForSolution() || false; 
         
}
   
// keep this function call here 
// to see how to enter arguments in JavaScript scroll down
ArrayAdditionI(readline());

It works by stepping through the array one by one, and tries both adding the current value & skipping it, exploring each possibility. It stops when it finds a working solution, otherwise returns false. Hope this helps! :-)

dsernst
answered on 09/24/14

If you want to spare yourself a 1,312 page book on algorithms for the moment... you may just try Googling "subset sum problem".

drewprice
answered on 09/21/14

Consider the case where: arr = [ 1, 2, 3, 5, 7, 8,10 ]; I compiled and ran your program with that case and it doesn't work. It outputs false when the answer is clearly true since there are lots of combination that equal to the largest value of 10: 7+3 = 10 8+2 = 10 2+3+5 = 10 7+2+1 = 10 Going through your program: largestval = 10; reduced arr = [ 1, 2, 3, 5, 7, 8 ]; sum = 26; Then your for loop checks: Does sum-arr[i] ==largestval, so that results in: Does 26 - 8 = 10? No (since it equals 18) Does 26 - 7 = 10? No (since it equals 19) Does 26 - 5 = 10? No (since it equals 21) Does 26 - 3 = 10? No (since it equals 23) Does 26 - 2 = 10? No (since it equals 24) Does 26 - 1 = 10? No (since it equals 25) Lastly, your second if statement checks if 26 = 10 which would not pass. And your final result is false. Can you see the problem? Basically, you're only checking for combinations of sum - one other value. You need to check for all possible combinations including 2 number combinations, 3 number combinations all the way up to N number combinations where N is the size of the array. Try again, and always check your logic - not just if the program passes the submission test. P.S. Hint: you might want to read a few books on Algorithms starting with Introduction to Algorithms by Cormen.

kimeshan
answered on 09/21/14

Ok thanks. And yeah i didnt really go through other solutions, I was just surprised, justifiably so. and thanks for the hint. I'll be sure to go read a 1,312 page book right now on algorithms. Thanks again!

WonderButt
answered on 09/21/14

Ah, well @drewprice just gave you a much better hint! It still wouldn't hurt to have a solid understanding of some algorithms in my opinion - it can save you a lot of head banging in the future from my experience. Good luck.

kimeshan
answered on 09/22/14

Here is my DP solution without using recursion


static String ArrayAdditionI(int[] A) {
        Arrays.sort(A);
        int n = A.length;
        int target = A[n-1];
        int MAX = A[0] >= 0 ? target + 1 : target + 1 + Math.abs(A[0]);
        int ZERO = A[0] >= 0 ? 0 : -A[0];
        boolean[][] D = new boolean[n][MAX];

        D[0][0] = true;
        for(int i=0; i<n; i++)  D[i][0] = true;
        D[0][ZERO] = true;
        for(int i=0; i<n; i++)  D[i][ZERO] = true;

        for(int i=1; i<=n-1; i++) {
            if(A[i-1] >= 0) {
                for(int j=1; j<=MAX-1; j++) {
                    D[i][j] = D[i-1][j];
                    if(j-A[i-1] >= 0) {
                        D[i][j] |= D[i-1][j-A[i-1]];
                    }
                }
            } else {
                for(int j=MAX-1+A[i-1]; j>=1; j--) {
                    D[i][j] = D[i-1][j];
                    if(j-A[i-1] >= 0) {
                        D[i][j] |= D[i-1][j-A[i-1]];
                    }
                }
            }
        }
        return D[n-1][MAX-1] ? "true" : "false";
    }

binfeng
answered on 06/24/15

Here's a solution using a bitwise operator. Using the bit representation of the length of the arguement -1 (to remove the hihest value), we can check all combinations of the array elements against the total


function ArrayAdditionI(arr) { 
let subtotal = 0;
let isSum = false;
let total = arr.sort(function(a,b){return (a > b)}).pop();
let newarr = arr
let power2 = Math.pow(2,newarr.length);
let returnarr = [];

 for (let i=1;i<power2;i++){
     subtotal=0;
     for (let j=0;j<newarr.length;j++){
         Math.pow(2,j) & i ? subtotal += newarr[j] : "";
     }
     if (subtotal == total){isSum = true}
 }
  return isSum;
}
   
// keep this function call here 
ArrayAdditionI(readline());

pastirk
answered on 11/17/17

Python DP solution with recursion


def ArrayAdditionI(arr): 
    arr.sort()
    
    mem = dict()
    
    def check_sum(n, sum):
        if n == 0:
            return 'false'
        if n == 1:
            return arr[0] == sum
        if (n, sum) in mem.keys():
            return mem[(n, sum)]
        else:
            f = check_sum(n - 1, sum) or check_sum(n - 1, sum - arr[n-1])
            mem[(n, sum)] = f
            return f
    return check_sum(len(arr) - 1, arr[-1])

louw49
answered on 05/22/18