3
\$\begingroup\$

Problem: https://www.hackerrank.com/challenges/the-birthday-bar/problem

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 matches 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.

Function Description

It should return an integer denoting the number of ways Lily can divide the chocolate bar.

s: an array of integers, the numbers on each of the squares of chocolate d: an integer, Ron's birth day m: an integer, Ron's birth month

Print an integer denoting the total number of ways that Lily can portion her chocolate bar to share with Ron.

Example: Lily wants to give Ron m =2 squares summing to d = 3. The following two segments meet the criteria:

enter image description here

Here is my brute force solution that enumerates all possibilities:

// Complete the birthday function below.
static int birthday(List<int> s, int d, int m) {
    int n = 0;
    for(int i = 0; i < s.Count; i++) {
        if(s.Skip(i).Take(m).Sum() == d)
            n++;
    }
    return n;
}

Question: any non brute-force solutions to this problem?

\$\endgroup\$
4
\$\begingroup\$

You basically always need to use brute force here. There is no other way. However, you can do it a bit more efficiently.

You're redoing the whole summation in every step of the loop. You don't need to. You can compute the total with one subtraction and one addition in each step of the loop. Like this:

static int birthday(List<int> s, int d, int m) {
    int n = 0;
    int t = s.Take(m).Sum();
    for(int i = 1; i < s.Count - m; i++) {
        if (t == d) n++;
        t = t - s[i - 1] + s[i + m];
    }
    return n;
}

I hope this makes sense, I never write C#. I got here because of your 'javascript' tag. The code might not work correctly, it is untested, but I hope you understand the intention.

However, I do think there's a bug in your code. You loop over the whole list, all the way to the end, where you cannot take m squares anymore. The sum() there might result in unexpected matches.

\$\endgroup\$
  • \$\begingroup\$ int t = s.Skip(0).Take(m).Sum(); <-- should this be s.Take(m).Sum()? \$\endgroup\$ – David May 31 at 16:32
  • \$\begingroup\$ You are correct. Some debate here, lol. stackoverflow.com/questions/56398235/… \$\endgroup\$ – David May 31 at 16:33
  • \$\begingroup\$ I don't know whether to remove Skip(0) or not, but the intention is to take the first m squares from the choclate bar. I'll remove it, it does seem superfluous. \$\endgroup\$ – KIKO Software May 31 at 16:36
  • \$\begingroup\$ skip(0) means to skip the first 0 element, which turns out to skip nothing, :) \$\endgroup\$ – David May 31 at 16:37
  • \$\begingroup\$ Yes, that's what I thought. Can't do any harm, but is not needed. \$\endgroup\$ – KIKO Software May 31 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.