# Birthday Chocolate

# Birthday Chocolate

Saikumar_P + 14 comments int getWays(int n, int* squares, int d, int m){ // Complete this function int sum[105]; int count=0; sum[0]=0; for(int i=0;i<n;i++)sum[i+1]=sum[i]+squares[i]; for(int i=0;i<=n-m;i++){ if(sum[i+m]-sum[i]==d){ count++; } } return count; }

shubham21 + 1 comment nice logic. +1

NiceBuddy + 3 comments [deleted]milczarek_r + 2 comments Same approach, but with iterators instead.

int solve(int n, vector < int > s, int d, int m){ int ways = 0; for(auto it = s.cbegin(); it != s.cend(); ++it){ if(d == std::accumulate(it, it + m, 0)) ways++; } return ways; }

viigihabe + 0 comments [deleted]

bryon_nicoson + 2 comments same approach in Java

static int solve(int n, int[] s, int d, int m){ int total=0; for (int i=0;i<=n-m;i++){ if(Arrays.stream(s, i, i+m).sum() == d) total++; } return total; }

Shubhanka + 1 comment Please explain the logic behind it.

ramji_vishnu_26 + 1 comment @shubhanka Using Arrays.stream method he sends a Array 's', starting index 'i' end index 'i+m' as range which returns a set of integers from Array 's' for that specified range then using sum() method he checks the sum to equals 'd', if conditon satifies it increase the total plus one.

kuntalravi91 + 2 comments *

*starting index is i=0 and end index is i+m=2 so the 2 index is excluded?? **bryon_nicoson + 0 comments the index range is inclusive of the start and end indices: [0, 1, 2].

we are looking at the set of chocolates from i to i+m and determining if that set meets our criteria. if it does, we increment total.

**then we increment i and look at the next set**, and so on until we have traversed the array.i like victorz's analogy below: it is a "sliding window."

i hope that helps.

tiwari_ravikumar + 0 comments Yes the 2 index is excluded.

asmai8faical + 0 comments Java 8 is always here , thank you :)

cvilladiegoa + 0 comments Same approach in C#

int total = 0; for(int i = 0; i <= s.Count - m; i++) { var segsSum = s.GetRange(i, m).Aggregate((a, b) => a + b); if(segsSum == d) { total++; } } return total;

victorz + 2 comments I used a sliding window, just like you, but there was no need to build a sum array.

https://www.hackerrank.com/challenges/the-birthday-bar/submissions/code/43358272sayanmanik_sm + 1 comment how is the logic working?

victorz + 1 comment It's a

**sliding window**.CurlyHurlyGirl + 1 comment Can you tell me how the logic works? I'm new and have many to learn.

victorz + 0 comments If you already have the sum of a subarray (like the starred elements in

`[***___]`

), then you can get sum of the subarray with indices shifted right by 1 (for the previous example,`[_***__]`

) by adding one element and subtracting another.Prince_sai's solution gets O(n) runtime in a different way: a cumulative sum array.

15B01A0577 + 0 comments how did u get dat kinda logic

Sentinal_prime + 1 comment please explain the logic

khirulislam_cse + 7 comments Here is the Java implemetation. We just need the starting index that we are working on. and every time there is an ArrayIndexOutofBoundsException that means we don't need the loop anymore and we break. We count the total of consecutive squares and check if it's equal to the d.

static int solve(int n, int[] s, int d, int m){ int startingIndex =0; int result =0; int total = 0; for(int i=0;i<n;i++){ startingIndex = i; try{ for(int j=0;j<m;j++){ total += s[startingIndex + j]; } }catch(Exception e){ break; } if(total == d){ result++; } total =0; } return result; }

codertoaster + 4 comments I have the same idea as you, but why are most of my test cases failing ?

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

pankajbabu + 1 comment i use yur code,but test case is fails.....so improve your codess.. thanks

pooniaarvind29 + 0 comments thug life

aishwarya217 + 0 comments Hey, it's probably not working because in this code

**i**is getting changed to**start + 1**and then getting incremented again as part of the**for**loop.if(sum == d) { num++; sum=0; i=start+1; start++; end++; } else { sum=0; i=start+1; start++; end++; }

Hope this helps.

rvrishav7 + 1 comment int main() { int n; cin>>n; int ar[n]; int i,c=0; for(i=0;i<n;i++) cin>>ar[i]; int d,m; cin>>d>>m; int s=0,l=1; i=0; while(m<=n) {l=0;s=0; while(l<m) { s=s+ar[l+i]; l=l+1; } if(s==d) { c=c+1; } i=i+1; n=n-1; } cout<<c; return 0; }

abhi_satya1357 + 0 comments # include

using namespace std;

int main() { int i,n,sum=0,date,month,num[1000],count=0,j; cin>>n; for(i=0;i>num[i]; } cin>>date>>month; for(i=0;i

romulo8000 + 0 comments A good constructive tip: extract common code like:

if(sum == d) { num++; } else { start++; } i=start+1; sum=0; start++; end++;

It's More readable

krmatalia + 1 comment int c=0; for(int i=0;i<n;i++) { int sum=0,j=i,lp=0; if((j+m)>=n && (j+m)!=1) break; else { while(lp<m) { sum+=s[j++]; lp++; if(sum==d) ++c; } } } return c;

even this is failing i don't know why when i purchased the testcases i was getting the right output.

codertoaster + 0 comments yeah that happens a lot. my outputs are same as the test cases still shows failure.

harshitha2922 + 0 comments thanks for an easy understood algorithm !

dparthib + 0 comments Nice code:

If you change your code as below suggestion then no need to handle the exception.

for(int j=0;(j<n)&&(j<m);j++)

ramji_vishnu_26 + 0 comments @Khirulislam_cse You can avoid using the entire try catch block by replacing with simple while loop statement.

Shubham_203 + 0 comments Hie,see this java implementation

static int solve(int n, int[] s, int d, int m){ // Complete this function int sum,count=0,j,k; for(int i=0;i<=n-m;i++) { k=i; sum=0; j=1; while(j<=m) { sum=sum+s[k]; k++; j++; } if(sum==d) count++; } return count; }

phatngo1606 + 0 comments Your code is so wonderfullll

sonupanchal + 0 comments [deleted]Nidhi99 + 0 comments Why is sum an array of 105 integers? Isn't 101 enough?

ash_upadhyay + 4 comments def solve(n, s, d, m): # Complete this function count = 0 for i in range(0,n): total = sum(s[i:m+i]) if total == d: count+=1 return count

This function uses a sliding window too :) If any corrections please comment :)

tpacker + 2 comments I believe this is O(n^2). O(n) is also possible.

ash_upadhyay + 1 comment @tpacker Thanks. I appreciate your response. Can you please help me understand how can we get O(n) I couldn't figure out what makes it O(n^2) any leads would really be appreciated :)

smhoyo + 3 comments So, your answer is not really O(n^2), but rather O(n*m), since your sum() method iterates over m elements in the array for every n element in the array. Thus, O(m*n).

You can improve though, if you figure out a smarter way to keep track of the sum of the m previous pieces. You can for example just hold a sum variable where you remove the last element and add the new one as you iterate, instead of calculating the whole sum each and every time. (Imagine the repeated work when your m grows).

Here is a java example:

static int solve(int n, int[] s, int d, int m){ int sum = 0; int r = 0; for (int i = 0; i < s.length; i++) { sum += s[i]; // M is never less than 1 if (i > m - 1) sum -= s[i - m]; if (i >= m - 1 && sum == d) r++; } return r; }

mountaingeek93 + 0 comments this is gold! thank you :)

victorz + 0 comments m <= n, so O(nm) is

*technically*O(n^2) too, but O(nm) is a tighter upper bound._rajulSingh + 0 comments wow

Ajey01 + 0 comments yeah!!

suryabteja + 0 comments Why is that it doesn't through list index out of range error?

Shanthini_S + 0 comments [deleted]mahamadbilal696 + 0 comments [deleted]

smhoyo + 1 comment My solution in Java:

static int solve(int n, int[] s, int d, int m){ int sum = 0; int r = 0; for (int i = 0; i < s.length; i++) { sum += s[i]; // M is never less than 1 if (i > m - 1) sum -= s[i - m]; if (i >= m - 1 && sum == d) r++; } return r; }

victorz + 0 comments This one uses a sliding window, just like my solution. I did it slightly differently by summing the first m digits in another loop.

johnmensah + 2 comments why not O(n) like below

def solve(n, s, d, m): if(n==1 and s[0]==d): return 1 elif(n==1): return 0 count = 0 for i in range(len(s)-1): if(sum(s[i:m+i])==d): count = count + 1 return count # Complete this function

mahamadbilal696 + 0 comments we should select the proper range otherwise the list becomes out of order, but in this example no need(can select range(0, n))

`def birthday(s, d, m, n): count = 0 for i in range(n-m+1): if(sum(s[i:m+i])==d): count = count + 1 return count`

Any quasions, fell free to ask.

not_neophyte + 0 comments can anyone pls explain how does this code work?

priyachowdary191 + 1 comment will you please explain why did you write this:sum[i+m]-sum[i]==d

Ajey01 + 0 comments i didn't have written this line.....plzz check once

shreyagarwal611 + 0 comments nice logic broo!!!

aiswarya110498 + 0 comments change getWays function into birthday function.. Answer is right.. Could you please explain the logic behind declaring sum[105] ?

kcoddington0925 + 4 comments C# implementation:

using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static int getWays(int[] squares, int d, int m) { int ways = 0; for (int i = 0; i < squares.Length - (m - 1); i++) if (squares.Skip(i).Take(m).Sum() == d) ways++; return ways; } static void Main(String[] args) { int n = Convert.ToInt32(Console.ReadLine()); string[] s_temp = Console.ReadLine().Split(' '); int[] s = Array.ConvertAll(s_temp, Int32.Parse); string[] tokens_d = Console.ReadLine().Split(' '); int d = Convert.ToInt32(tokens_d[0]); int m = Convert.ToInt32(tokens_d[1]); int result = getWays(s, d, m); Console.WriteLine(result); } }

kandoimihir + 1 comment I know this is an old comment but I want to understand the logic behind this

squares.Length - (m - 1)

Can you help me?

StefanCFC + 1 comment If n = 19 and m = 7. You don't need to sum elements from index 13 to 18 because you don't have enough peaces of chocolate. I hope i helped you :D

kandoimihir + 0 comments Thank you :)

marlondias + 0 comments Cool LINQ! Thanks for sharing!

rodrigoramirez93 + 0 comments Solid as a rock, thanks for sharing

audusheriffemor1 + 0 comments Hello, I'm confused. Why did you have to subtract

*(m - 1)*from the length of the array

PkkdGuy + 8 comments Pyhton people see this!!

def getWays(squares, d, m): tp = (len(squares)-m) + 1 #total number of pieces possible return len([1 for i in range(tp) if sum(squares[i:i+m])==d])

saxtouri + 1 comment I did the same think with multiple lines, but it's always refreshing to see oneliner solutions.

tkomane + 3 comments Honestly I find one-liners a bit overrated. A lot of people on here get into this nasty habit of cramping their code just to force a one-liner - which I find just silly.

jon_black + 0 comments I agree and disagree. One-liners that don't obfuscate the code are succinct. You just have to make sure that property holds true, and that creating a one-liner doesn't decrease performance.

saxtouri + 0 comments One liners make a slipery slope when writting production code, but in games like this, it is just a nice excescise.

Pyjamadeus + 1 comment Seeking out a one-liner at the expense of efficiency (as we see here) seems a strange way to prioritise things, but oh well

sharmaspg + 1 comment how do you people get this logic ?is it pure practice or do you refer some books for the logic ?

SpaceHero + 0 comments I suppose practice. Practice list comprehensions enough and it can get easy. This is a list comprehension that adds 1 to a list everytime the sum in that range is equal to d. Then len is used to count all the 1s in that list. I learned list comprehensions through learning haskell.

pnkj119 + 4 comments Beat this:

def getWays(squares, d, m): return sum([1 for i in range(n-m+1) if sum(s[i:i+m])==d])

PkkdGuy + 1 comment There is nothing to beat in your code bro :D

victorz + 3 comments You could use a generator expression instead of a list comprehension.

def getWays(squares, d, m): return sum(1 for i in range(n-m+1) if sum(s[i:i+m])==d)

But if you want a more efficient solution for larger inputs, use a sliding window (see the following link). https://www.hackerrank.com/challenges/the-birthday-bar/submissions/code/43358272

SebastianNielsen + 1 comment By "sliding window" don't you mean a loop whithin a loop, so that it counts a surden amount ahead for each item in the lst.

victorz + 1 comment By "sliding window", I mean one loop without nesting another loop within it. When you advance to the next item, you add one item and subtract another item.

jeremydcarr + 0 comments Yo, thanks for that description. I hadn't thought of that. Made the solution so much cleaner.

h201551072 + 1 comment can u explain ur code pls!!!!!

victorz + 0 comments There's nothing to explain; it's all obvious.

sinamanbons + 0 comments return sum(sum(s[element:element+m) == d for element in range(len(s))])

vishoo7 + 0 comments This is adding from idx to idx + m. It's more efficient to keep a running sum and subtract the beginning of the window and add the next value:

def solve(n, s, d, m): if m > n: return 0 i = j = 0 window_sum = 0 while j < m: window_sum += s[j] j += 1 count = 1 if window_sum == d else 0 while j < n: window_sum -= s[i] window_sum += s[j] if window_sum == d: count += 1 i += 1 j += 1 return count

joshumcode + 0 comments I don't understand how this works given that n is not defined.

alphasingh + 0 comments Python people saw this, and now python people jealous. :p

baymaxneoxys + 0 comments Thanks for the approach! BTW we could have used segment trees as well, right?

LeHarkunwar + 2 comments Did similarly, but shorter

def solve(n, s, d, m): return sum([1 for i in range(n-m+1) if sum(s[i:i+m]) == d])

victorz + 2 comments That's just a copy of https://www.hackerrank.com/challenges/the-birthday-bar/forum/comments/289156

LeHarkunwar + 0 comments Truly didn't see that, looks super similar :P

cfshao_bjtu + 1 comment I cannot see the results in the link. Could you please share your code here?

Thank you

cfshao_bjtu + 0 comments

bL4ck_r4bb1t + 0 comments In Python True == 1 and False == 0, so this also works:

def solve(n, s, d, m): return sum(sum(s[i: i + m]) == d for i in range(n - m + 1))

panda_whisperer + 1 comment Ruby version:

def solve(squares, d, m) squares.each_cons(m).map(&:sum).select { |s| s == d }.count end

brunoao86 + 0 comments +1

Ruby <3

juggmug + 0 comments how did u write tp?

arisiru + 0 comments In fact your solution is dumb, you solved it in O(n^2) instead of O(n)

lahouari + 7 comments My java simple way...

static int solve(int n, int[] s, int d, int m) { int result = 0; for (int i=0; i<n; i++) { int limit = i + m; if (limit > n) { break; } int sum = 0; for (int j=i; j<limit; j++) { sum += s[j]; } if (sum == d) { ++result; } } return result; }

ScienceD + 0 comments What do you think about recursive approach?

int solve(vector<int> s, int d, int m, int i) { if(i < s.size() - m + 1) { int sum = 0; for(int j = i; j < i+m; ++j) sum += s[j]; bool good_choco = sum == d; return good_choco + solve(s, d, m, i+1); } else return 0; }

lchoo1996 + 0 comments [deleted]priyangshuy + 0 comments love your code.

VirajSingh19 + 0 comments I was doing the same thing and my code was throwing array out of bounds exception. I don't know where I was wrong until I saw your code. It happens to me all the time.

harshshubh + 0 comments Thank you for your advice.

afederigo + 0 comments I have pressed dislike accidentally, sorry!

sss1721 + 0 comments Really awesome. Superb Logic

Coder_AMiT + 1 comment One liner is always better, but i dont really like to compress the size, moreover this is more readable:

def getWays(squares, d, m): count = 0 for i in range(0,len(squares)+1-m): if sum(squares[i:i+m]) == d: count+=1 return count

girishpillai239 + 1 comment why is the range subtracted from len()+1?

Coder_AMiT + 0 comments so that when the sliciing happens on list squares[i:i+m] , it does not go above the index limit. as you can see i am doing i+m , while i is going from 0, to len() In such case, you need to reduce the window. This is known as Sliding window algorithm.

lokeshwaran100 + 1 comment I hope the below solution is in O(n):

int getWays(vector < int > squares, int d, int m){ int sum = 0; int index = 0; int getway = 0;

`for(int i = 0; i < squares.size(); i++){ sum += squares[i]; if(m == (i - index + 1)){ if(d == sum){ getway++; } sum -= squares[index++]; } } return getway;`

}

kpa_rukmangatha1 + 1 comment i think this wont work. you're simply adding value at an index to sum and subtracting it back at the end.I think this will not slide. plz explain if it works. thanks!!

lokeshwaran100 + 0 comments Yes, this works for me. I'm not subtracting for all the iteration. Substraction is done only when the required number of consecutive element are processed. This substraction allows me not recalculate the sum everytime, as it already hold the summed value of consecutive element. To calculate the next set of summation, I just need to subtract the 1st added element.

gsuaki + 1 comment function reduce(pieces) { return pieces.reduce((sum, val) => sum += val, 0); } function solve(n, s, d, m) { var count = 0; for (var i = 0; i < n; i++) { if (reduce(s.slice(i, i + m)) === d) count++; } return count; }

ser_zhile + 0 comments You could optimise it a bit as there is no need to go fully to the end of the array each time

for (var i = 0; i <= n-m; i++) { if (reduce(s.slice(i, i + m)) === d) count++; }

robertklee + 0 comments Here is mine in Java, which I believe mine is only O(n).

static int solve(int n, int[] s, int d, int m){ // Complete this function int total = 0; // the sum int len = 0; // the current length (window = length of m) int start = 0; // the starting index of the window int count = 0; // the count for(int val: s) { if(total < d && len < m) { total += val; len++; } else { total = total - s[start] + val; start++; } if(total == d && len == m) count++; } return count; }

b_pritam + 1 comment hello friends. its my solution in c.

# include

int main() { int n,d,m,a[100],i,k,j,s,b=0; scanf("%d",&n); for(i=0;i

i think this code is quite easy to understand.

secretmafioa + 0 comments ohhh....pateli....Sir!!!

ryukato79 + 0 comments Here scala code is

pieces.sliding(m).filter(s => s.sum == d).size

Sort 648 Discussions, By:

Please Login in order to post a comment