Algorithms 101: Birthday Chocolate in JavaScript

Noob v. Algorithms #10, array manipulation

So there’s this girl, Lily. She wants to give her pal chocolate for her birthday, but there are conditions!

Here’s the problem in HackerRank:

For those of you who learn better with pictures, read on. In the sample input below, 5 is the number of squares in the chocolate bar; the second line is the integers in those squares; the third line is his birth date(3) followed by his birth month(2).

Here’s how we start:

function birthday(s, d, m) {
     // s = array of integers 
     // d = date  
     // m = month
}

Observations/ Choose your weapons …

Things to notice:

1. The integers have to be contiguous — which means we need to preserve the order of the array. So we probably won’t be using .sort(); but we will be using a loop.
2. We need m integers in a row to add up exactly to d, so as we loop, we are going to want to look at the sum of m contiguous integers at a time. If you want to look at just part of an array, in order, slice() is your tool!

Break the problem up into smaller problems

We will only give away chocolate if we have m contiguous squares adding up to d. Assuming we have at least m squares (that’s an edge case we can check for later), here’s what we have to do:

1. loop through one slice of the array at a time; slice has a length of m
2. get the sum of that slice
3. if the sum equals date, increment a counter
4. return the counter

Step 1. Let’s Loop and slice() …

Slice is slightly tricky! It takes two arguments, a starting index and an ending index. Your slice will end just before the ending index. Documentation here.

So array.slice(0,2) gives you a ‘slice’ of the array from the 0th index up to but not including index 2:

let array = [apple, bobcat, couch]
let slice = array.slice(0,2)
// slice = [apple, bobcat] 

In our code, we want to examine the sum of the current index plus the next two indexes, so our slice will look like this:

function birthday(s, d, m) {

     for(let i = 0; i < s.length - 1; i++){
          let subArray = s.slice(i, i+m)
          if subArray.length === m {
             // more code here

          }

     }

}

Note: if you are looping over an array one item at a time, starting at the first index (i = 0) and you stop at the end, where the index is array.length — 1.

In our case, we want to make sure we are always looking at m number of squares at a time. If m is 5, for example, and our loop continues until we start our slice at the last element, we are not going to get 5 integers; we’re going to get just the last element.

We can account for this by setting the maximum value for i at: i < s.length — 1 — m. BUT for reasons this Noob can’t figure out, doing that makes the algorithm fails some of HackerRank’s tests. Please comment if you know why!!

As a workaround, I added an extra if statement to check that my subArray’s length is in fact equal to m.

function birthday(s, d, m) {

     for(let i = 0; i < s.length - 1; i++){
          let subArray = s.slice(i, i+m)
          if subArray.length === m {
             // more code here

           }

     }

}

Step 2. Get the sum of the slice

This is a perfect place to use JavaScript’s reduce() method.

let sum = subArray.reduce((a,b) => a + b, 0)

Step 3. if the sum equals date, increment a counter

To increment a counter, we have to set one up. We’ll set ours up before the loop, operate on the counter during the loop, and then return the counter after the loop.

Inside the loop, we’ll increment like so:

if(sum === d){
     counter += 1
}

So far, our code looks like this:

function birthday(s, d, m) {
    let counter = 0

    for(let i = 0; i < s.length - 1; i++){
          let subArray = s.slice(i, i+m)
          if subArray.length === m {
             let sum = subArray.reduce((a,b) => a + b, 0)
             if(sum === d){
                  counter += 1          
              }
           }
     }

     return counter
}

and now, for the edge cases ….

Edge cases are the odd ones — for instance, what if your array, s, included some letters, not just digits? or what if s weren’t always an array etc? It’s easy to go overboard imagining what could possibly be wrong with the inputs.

After a few weeks of solving algorithms for several hours a day, 5 days a week, I began to notice that you can save a lot of time by reading directions carefully. The directions often rule out possible edge cases.

For this problem, here are HackerRank’s notes about the inputs and their constraints:

In other words, we can always expect integers, in certain ranges.

Within these parameters, however, there are still special cases. What if the birth month is November? In that case, m equals 11, and we are looking for 11 contiguous squares of chocolate whose integers add up to d. But if we have fewer than 11 squares of chocolate, no matter what the integers are, we won’t succeed.

We can deal with that edge case like so:

//edge case, month greater than # of squares in bar

let counter = 0;

if(m > s.length ){
     return counter
}

Another edge case:

What if the birth month is January, and there’s only one square of chocolate? Then the integer on that square must equal that date. We can handle this edge case like so:

//edge case month is one, only one square of chocolate.

if(s.length === 1 && m === 1){

     if (s[0] === d) {

          return 1
     }
}

All together now:

function birthday(s, d, m) {

     //edge case #1, m > squares of chocolate
     let counter = 0;
     if(m > s.length ){
           return counter
     }

     //edge case #2, month is jan, only one square of choc.
     if(s.length === 1 && m === 1){
          if (s[0] === d) {
               return 1
          }
      }

     for(let i = 0; i < s.length - 1; i++){
          let subArray = s.slice(i, i+m)
          if subArray.length === m {
             let sum = subArray.reduce((a,b) => a + b, 0)
             if(sum === d){
                  counter += 1          
              }
           }
     }

     return counter
}

It works! And now I’m thinking about chocolate ….

Copyright © Joan Indiana Lyness 2019

Next: Algorithms 101, #11, Princesses, Peas & Recursion in Ruby

in case you missed it: Algorithms 101, #9, Jewels and Stones in Ruby and JavaScript