We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

intgetWays(intn,int*squares,intd,intm){// Complete this functionintsum[105];intcount=0;sum[0]=0;for(inti=0;i<n;i++)sum[i+1]=sum[i]+squares[i];for(inti=0;i<=n-m;i++){if(sum[i+m]-sum[i]==d){count++;}}returncount;}

can U explain me about 2 lines of your code?:
for(auto it = s.cbegin(); it != s.cend(); ++it){
if(d == std::accumulate(it, it + m, 0))
I think a accumulate will sum element out of vector, I think it will be it != cend() - m more saver.

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

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

because the last pair formed will be of the size m and we need out loop to go till n-m . if we go forward (n-m) even one step then m size of pair will not be formed as there are no more elements in array

Can I ask you why? Because I think the condition: <= s.length - m will make the accumulate in belong the size of vector, I dont understand a code with same like you said like this:
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;
}

Is it me or this is not the "same approach"? Correct me if i'm wrong but i think Arrays.stream.sum() iterates fron index a to b, so in every iteration of the for loop you are iterating again. Your algorithm is not 0(n) as @Saikumar_P's. This is my 0(n) solution with Java similar to @Saiumar_P's:

static int birthday(List s, int d, int m) {

int[] sums = new int[s.size() + 1];
int count = 0;
for(int i = 0; i < s.size(); i++) {
int sumsIndex = i + 1;
sums[sumsIndex] = sums[sumsIndex - 1] + s.get(i);
if (sumsIndex >= m && (sums[sumsIndex] - sums[sumsIndex - m]) == d)
count++;
}
return count;
}

int count = 0;
for (int i = 0; i < s.size() - m + 1; i++) {
int sum = 0;
for (int j = 0; j < m; j++) {
sum = sum + s[i + j];
}
if (sum == d) {
count++;
}
}
return count;

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.

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.

staticintsolve(intn,int[]s,intd,intm){// Complete this functionintsum,count=0,j,k;for(inti=0;i<=n-m;i++){k=i;sum=0;j=1;while(j<=m){sum=sum+s[k];k++;j++;}if(sum==d)count++;}returncount;}

@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 :)

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:

staticintsolve(intn,int[]s,intd,intm){intsum=0;intr=0;for(inti=0;i<s.length;i++){sum+=s[i];// M is never less than 1if(i>m-1)sum-=s[i-m];if(i>=m-1&&sum==d)r++;}returnr;}

Im not sure of this solution. This will not be working with this input:

51213332

The output should be 2 but will be 3 because it will count last digit of the series 3. This solution does not consider what if solution will be shorter than a month digit.

Sure, this will pass all validators but still... :).

This method wouldn't work if the numbers were not close together? I tested it for an array with suiting numbers in the opposite side of the array and sure enough it didn't work.

So, is there a way to find the anwer for this case?

staticintsolve(intn,int[]s,intd,intm){intsum=0;intr=0;for(inti=0;i<s.length;i++){sum+=s[i];// M is never less than 1if(i>m-1)sum-=s[i-m];if(i>=m-1&&sum==d)r++;}returnr;}

defsolve(n,s,d,m):if(n==1ands[0]==d):return1elif(n==1):return0count=0foriinrange(len(s)-1):if(sum(s[i:m+i])==d):count=count+1returncount# Complete this function

## Birthday Chocolate

You are viewing a single comment's thread. Return to all comments →

nice logic. +1

Same approach, but with iterators instead.

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

The OP is O(n)

It's O(nm).

its o(n^2), coz in worst case senario, all the choclate blocks would add up to d.

I have implemented it in O(n).

can you show your logic ???

Why call accumulate function every iteration when you add only one square ? It's not the same approach : you are O(nlog(n)), his solution is in O(n)

can U explain me about 2 lines of your code?:

`for(auto it = s.cbegin(); it != s.cend(); ++it){ if(d == std::accumulate(it, it + m, 0))`

I think a`accumulate`

will sum element out of vector, I think it will be`it != cend() - m`

more saver.same approach in Java

Please explain the logic behind it.

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

*

starting index is i=0 and end index is i+m=2 so the 2 index is excluded?? *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.

For the same program, how can we get the result if the required chocolate squares are not consecutive?

thats not what the problem states ( these types of problem are called maximum-sub array problems ) ,

Still you want to solve this problem, you need to use Combinations, which will increase the diffuculty.

what is the i < n-m?

Yes the 2 index is excluded.

Java 8 is always here , thank you :)

what if we must find when numbers not consecutive?

for example input:

10

5 3 1 4 2 5 1 2 4 2

8 2

there we can got 8 like that:

5 3

4 4

That would be the subset sum problem, with a limit on the size of the subset.

why i<=n-m is used for?

because the last pair formed will be of the size m and we need out loop to go till n-m . if we go forward (n-m) even one step then m size of pair will not be formed as there are no more elements in array

JS approach

Nice Logic!

really nice logic..Thanks(:..

I think s.length - m + 1 is not necessary, can be just s.length.

Can I ask you why? Because I think the condition:

`<= s.length - m`

will make the accumulate in belong the size of vector, I dont understand a code with same like you said like this:`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; }`

Thanks mate!!

Don't call sum() every time Oo You add only one square each time ! (reduction cost log(n) computation) → O(nlog(n)) It's possible in O(n) complexity

Is it me or this is not the "same approach"? Correct me if i'm wrong but i think Arrays.stream.sum() iterates fron index a to b, so in every iteration of the for loop you are iterating again. Your algorithm is not 0(n) as @Saikumar_P's. This is my 0(n) solution with Java similar to @Saiumar_P's:

What is n here?

Beautiful solution, one thing learned today! Thank you!

So i have implemented this piece of code but keep getting an error: "no suitable method found for stream(List,int,int)"

Same approach in C#

In C++

int count = 0; for (int i = 0; i < s.size() - m + 1; i++) { int sum = 0; for (int j = 0; j < m; j++) { sum = sum + s[i + j]; } if (sum == d) { count++; } } return count;

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/43358272

loved your code.

loved your code.

how is the logic working?

It's a

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

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.

how did u get dat kinda logic

please explain the logic

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.

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

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

thug life

lol

lol

Hey, it's probably not working because in this code

iis getting changed tostart + 1and then getting incremented again as part of theforloop.Hope this helps.

thats what it was for me, thank you

## 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

A good constructive tip: extract common code like:

It's More readable

Nice logic man, i learn some new tips there.thank you for posting this.

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

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

thanks for an easy understood algorithm !

Nice code:

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

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

Hie,see this java implementation

Your code is so wonderfullll

Why is sum an array of 105 integers? Isn't 101 enough?

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

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

@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 :)

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:

this is gold! thank you :)

m <= n, so O(nm) is

technicallyO(n^2) too, but O(nm) is a tighter upper bound.wow

Awesome solution. Some out of the box thinking there!!

yeah!!

Why is that it doesn't through list index out of range error?

The shortest method for the above python code

return sum(1 for x in range(len(s)) if sum(s[x:x+m]) == d)

Well done!

Im not sure of this solution. This will not be working with this input:

The output should be

`2`

but will be`3`

because it will count last digit of the series`3`

. This solution does not consider what if solution will be shorter than a month digit.Sure, this will pass all validators but still... :).

That't beutiful thank you for sharing : i did this way but we can make way shorter by yours..

List comprehension is amazing

I agree but also his method is n * m time complexity sadly.

This method wouldn't work if the numbers were not close together? I tested it for an array with suiting numbers in the opposite side of the array and sure enough it didn't work.

So, is there a way to find the anwer for this case?

My solution in Java:

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

why not O(n) like below

-1 That's O(nm), not O(n).

The reason is that your sum is an iterative function.

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

Any quasions, fell free to ask.

perfect code

Very inefficent.

can anyone pls explain how does this code work?

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

i didn't have written this line.....plzz check once

nice logic broo!!!

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

nice logic. However can you reduce the time complexity a little?

No, it's already O(n).

Ruby!

Can you explain me the question in easy language ,i mean what we have to do.

please explain the logic

nice pal

could you explain the second for loop

May I get Algo Explaination pls...