Leaena

Solver of Problems

Aug
12

I figured it out! Sort of on my own, sort of studying how others had “solved” it in different languages (a few of the “solutions” didn’t seem to work). Array Addition I is now my bitch. Also the next 10 easy problems from Coderbyte are on my GitHub. 6 more to go (well 7 actually, I gave up on ArithGeo, but the solving of Array Addition gives me hope that I will figure it out tomorrow). Problem description: 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. And my solution: (basically grabs the largest value out of a provided array and it runs through all the possible sum combinations of all the other numbers to see if one of those sums equals the largest values)

function ArrayAdditionI(arr) { 
  arr.sort(function(a,b){return a - b})
  var largest = arr.pop();
  var sum = 0;

  for (var i = 0; i < arr.length; i++){
    sum += arr[i];

    for (var j = 0; j < arr.length; j++){
      if (i != j) {
        sum += arr[j];
        if (sum == largest) {
          return true;
        }
      }
    }

    for (var k = 0; k < arr.length; k++) {
      if (i != k) {
        sum -= arr[k];
        if (sum == largest) {
          return true;
        }
      }
    }

    sum = 0;
  }

  return false;      
}
  • Jay Kan

    Hey Congrats on getting accepted by Hack Rector Leaena!

    I just wanted to let you know that on line 2, you forgot to include the “return” keyword within your sort( ) method for ascending the numbers. I believe the correct way should be: arr.sort(function(a,b) { return a – b } );

    Cheers,
    Jay Kan

  • Jee

    I got stuck on this problem too. I have seen a lot of solutions for this particular question and every one of them has: arr.sort(function(a,b){return a – b}). I understand that sort method is necessary. But why is function(a,b){return a-b} needed?

    Anyway, I am so glad that I found your blog, Lindsey. I am in the interview process for a coding bootcamp as well. Your blog posts have been super helpful and interesting.

  • Adrian

    Lindsey,
    I, like many others, found that challenge to be really hard. I found your solution. I tried it on [1, 2, 20, 30, 40, 50, 61] and got false. But the array contains [1, 20, 40] to make 61. When I tried [1, 20, 30, 40, 50, 61], which is trivially different, I got true. Do you know what is going on?

    • Sadly, it’s because the solution is imperfect. I find Lindsay’s drive to learn programming very inspiring, so I was tempted not to post this at all, but the solution is incomplete. The crux is the way that it scans across, adding the values, and then scans the same way removing them – this covers most of the bases, but misses scenarios where you have to “jump” values (in your arrays, Adrian, she would have to “jump”/skip the 2).

      That said, this question is really unfair in its category. It’s taught in Computer Science Algorithms courses, which are focused on mathematics. More exactly, it’s typically taught after introducing a concept known as Dynamic Programming; at this point most of the students have two things: 1) they’ve been programming for several years, and 2) they’ve been doing the math in school (including the first ~half of the Algorithms course in which they’re learning this concept). So it feels terribly unfair to me for this sort of question to be listed under “Easy”.

      That said, there is a slow, naive solution that might be what the coderbyte folks assumed people would go for. I would still disagree with them on this assumption, as it still feels pretty math-based and outside the typical thought process of beginners, but here it is:

      (In Ruby, rather than Javascript, since some of the useful methods are already provided):

      ——————————————————————————

      def ArrayAdditionI(arr)
      largest = arr.max
      # Commented because it isn’t clear to me that they wanted the largest item actually removed:
      # arr.delete(largest)

      # For every integer between 2 and the array’s length, return the first item that matches:
      smallestMatchSize = (2..arr.length).find do |subsetSize|

      # Iterate over every possible combination of items of that length:
      arr.combination(subsetSize).find do |subset|

      # And see if the sum of every item in this combination, is the target:
      subset.reduce(:+) == largest
      end
      end

      !smallestMatchSize.nil? # Check if a result exists
      end

      ——————————————————————————

      The #s are comments in Ruby. Basically, if I pull the few comments out, here’s the wordy version of the algorithm:

      For every integer between 2 and the array’s length,
      Iterate over every possible combination of items in the original array of that length,
      And see if the sum of every item in this combination, is the target (largest item).

      When anything resolves true in the last (deepest) step, `find` stops iterating and returns it. Which, then it propagates up a step, because it’s also in a `find`, and finally to the top.

      This would be easy to convert into Javascript if you implement a combinations function that takes an Array, and a length, and returns all of the possible combinations up to that length. (Beware, the resulting Array can be huge!)

      Newer versions (ES6) of Javascript could implement the `combination` method very well with its generators/iterators, but that’s another story and going way off on a tangent.

      • Lindsey

        Please feel free to correct where you see fit! These posts are almost two years old and I haven’t looked at them since. The point of them was for learning so if that learning can be updated I’m grateful! 🙂

  • Alexius

    Hey Lindsey how was your Hack Reactor experience? I’m grinding my way through the Coderbyte Challenges in preparation for their test too. I’m not in SF so I’m doing the online remote pgm. Was their test super hard? I’ve read everywhere they have one of the smallest acceptance percentages; but, I have visualized my success. Like others I got stuck on this ArrayAdditionI(arr) challenge. After spending an hour with trying different things I figured I’d seek help too. Some of the elements in your program I have; however, I totally didn’t think of sorting the darn array and popping out the last element as the largest. I knew I needed to remove it from the array and store it somewhere before determining if the other items summed its value. Geesh this coding life is so cray; but, I’m having fun. Thanks for sharing your result. Congratulations since I’m sure you’ve finished the HR program already. Cheers!