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.
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;
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 aaccumulatewill sum element out of vector, I think it will beit != cend() - mmore 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 - 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; }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;