HackerRank Problem: Birthday Chocolate

This is a HackerRank Problem. You can find it HERE

This is actually a very easy problem. I have decided to write a blog on it to remind myself of a mistake that I did when solving this.

Task Description

Lily has a chocolate bar that she wants to share it with Ron for his birthday. Each of the squares has an integer on it. She decides to share a contiguous segment of the bar selected such that the length of the segment mathches Ron's birth month and the sum of the integers on the squares is equal to his birth day. You must determine how many ways she can divide the chocolate.

Consider the chocolate bar as an array of squares, $s = [2, 2, 1, 3, 2]$. She wants to find segments summing to Ron's birth day, $d = 4$ with a length equalling his birth month, $m = 2$. In this case, there are two segments meeting her criteria: $[2, 2]\ and\ [1, 3]$.

Assumption

Chocolate bar has at least the length of 1. $i.e.$ The input $array\ length >= 1$.

Initial Solution (Fails For an Edge Case)

  static int solve(int n, int[] s, int d, int m) {
    int i = 0, j = 1;
    int sum = s[i];
    int counts = 0;
    for(; j < s.length; j++) {
        sum += s[j];
        
        if (sum > d) {
            sum -= s[i];
            i++;
        } else if (j - i == m - 1) {
            if (sum == d) counts++;
            sum -= s[i];
            i++;
        }
    }
    return counts;
  }

Simple isn't it? But it fails for an EDGE case. Can guess the Edge Case?

The Edge Case

Well the edge case is, in the code we have initialized sum as the first element of the array and as soon as we enter the loop we increment the sum with the second element of the array. This means we never consider the case where $m == 1$.

Actual Solution

We can solve this by initially considering NO any elements. We will start considering elements only after we start loop. So the only changes to be made are

int j = 0; // instead of j = 1;

and,
int sum = 0; // instead of sum = s[i]

  static int solve(int n, int[] s, int d, int m) {
    int i = 0, j = 0;
    int sum = 0;
    int counts = 0;
    for(; j < s.length; j++) {
        sum += s[j];
        
        if (sum > d) {
            sum -= s[i];
            i++;
        } else if (j - i == m - 1) {
            if (sum == d) counts++;
            sum -= s[i];
            i++;
        }
    }
    return counts;

}

Complexity

The solution solves the problem in one pass without using extra memory. So the time complexity is $\cal{O(n)}$ and the space complexity is $\cal{O(1)}$.

---

---

---