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

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.

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;}

yeah. that's the power of c++ stl.

Please explain the logic behind it.

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

why i<=n-m is used for?

JS approach

function birthday(s, d, m) {
    var count = 0;
    for (var i = 0; i < s.length - m + 1; i++){
        var sum = 0;
        for (var j = 0; j < m; j++){
            sum = sum + s[i + j];
        }
        if (sum == d) {
            count++;
        }
        
    }


    return count;
}

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:

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;       
}

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

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;

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.

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

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.

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

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.

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

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

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

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;
}

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

List comprehension is amazing

can u explain wht this "1" is doing in sum( "1" for x in range(len(s)-m+1)

Very inefficent.