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.
let reducer = (a, c) => a + c;
let count=0;
for(let i=0; i<s.length; i++){
let temp = s.slice(i, m+i);
if(temp.reduce(reducer) == d){
count++;
}
}
return count;
in JS
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.
int birthday(vector s, int d, int m) {
int n = 0;
for(int i = 0; i <= s.size() - m;i++){
if( d == accumulate(s.begin() +i, s.begin() + i + m, 0)){
n++;
}
}
return n;}
@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;
}
ya wht if we get sum=d at fisrt position.
like if ex.5,1,3,4,2.hera d=5and m=2;
at the step sum =sum+s[i+j];
here i=0and j=0;
then the counter increases but .its not correct,we should take two
bars to sum d.
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;
static int birthday(List<Integer> s, int d, int m) {
int sum = 0,ways=0;
for (int i=0;i<m;i++){
sum += s.get(i);
}
for (int i=0;i<s.size()-m+1;i++) {
if (sum==d) {
ways++;
}
if (i+m <s.size()){
sum =sum-s.get(i)+s.get(i+m);
}
}
return ways;
}
The second loop was iterating through the list to calculate the sum of each subarray of size m by removing the first element and then adding the m'th element back. If that makes sense.
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.
How do we find out the time complexity. someone pls help me out
I have implemented it in O(n).
can you show your logic ???
function birthday(s, d, m) {
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 aaccumulatewill sum element out of vector, I think it will beit != cend() - mmore saver.Greate! Nice usage of accumulate!
what you did but more readable:
int birthday(vector s, int d, int m) { int n = 0; for(int i = 0; i <= s.size() - m;i++){ if( d == accumulate(s.begin() +i, s.begin() + i + m, 0)){ n++;} } return n;}
sorry, dont know how to make the code look nice in this forum :-/
yeah. that's the power of c++ stl.
lol
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.
Thank you
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.
Though I would say Hi from ACR.
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 - mwill 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; }but the real issue comes for the test case: (s,d,m) => (4, 4, 1)
it is necessry beacuse when you are not writing then error is index out of bound
Thanks mate!!
int i,j,sum,count=0,n=s_count; for(i=0;i<=n-m;i++) { sum=0; for(j=i;j
Mine is in a fimiliar way.
thanx man
thanks bro your logic is simple as well as ez :)
what if the sum exceed the d before the m is looped till the end!!! we can ignore further looing and make it more effecient !!
ya wht if we get sum=d at fisrt position. like if ex.5,1,3,4,2.hera d=5and m=2; at the step sum =sum+s[i+j]; here i=0and j=0; then the counter increases but .its not correct,we should take two bars to sum d.
nice one ....
Nice Logic
This will not work for this case:
1,2,1,3,2 d=3 m=2
Can you please expain why we have to use s.length-m+1 ???
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;
Please can you explain your code in details
The first loop was initializing the sum.
The second loop was iterating through the list to calculate the sum of each subarray of size m by removing the first element and then adding the m'th element back. If that makes sense.
I cleaned it up with Linq.
Good job