Machine Learning, AI and Programming

Leetcode : Consecutive Numbers Sum

Problem Statement


The brute force approach is to evaluate all possible sequence of consecutive numbers less than N, whose sum gives N. The number of all possible sequences of consecutive numbers less than N is O(N2), because we can select pair of indices i and j (i <= j) such that the sequence lies between i and j. The number of such pairs is O(N2). We can definitely improve on this run-time complexity by using the following observation:

If there is a sequence of M consecutive numbers such that their sum is N, then we can write it as (for some integer 'x'):

x + (x+1) + (x+2) + ... + (x+M-1) = N

Mx + 0.5*M*(M-1) = N

Also note that for each possible M, there is only one sequence of consecutive numbers of length M, whose sum is N, because if x + (x+1) + (x+2) + ... + (x+M-1) is a sequence of length M, then an alternate sequence of length M, can be obtained by either:

(x+1) + (x+2) + (x+3) + ... + (x+M) = N + M


(x-1) + (x) + (x+1) + ... + (x+M-2) = N - M

So none of the above sums to N.

Thus given that our consecutive sequences satisfy the below equation:

Mx + 0.5*M*(M-1) = N, for some integers M and x

Therefore we only need to iterate over the possible values of M, and count for how many of those, 'x' comes out to be an integer, i.e. (N-0.5*M*(M-1)) is divisible by M.

Now regarding different values of M, observe that N should be at-least as great as 0.5*M*(M-1), i.e.

N >= 0.5*M*(M-1) or M <= sqrt(2N)

Thus we only need to scan sqrt(2N) different possible values of M. Thus the run-time complexity is O(sqrt(N)). The python code is as follows:

import math
class Solution(object):
    def consecutiveNumbersSum(self, N):
        m = int(math.sqrt(2*N))
        cnt = 0
        for i in range(1, m+1):
            u = 0.5*i*(i-1)
            if N > u and (N-u) % i == 0:
                cnt += 1
        return cnt

Although the run-time complexity remains same, I tried to come up with another approach which does not require to compute the terms 0.5*m*(m-1) for each possible value of m between 1 to sqrt(2N). This reduces the run-time to a certain extent.

The idea is that if both M and M+1 satisfy the equations for some integer 'x' and 'y' respectively, i.e.:

Mx + 0.5*M*(M-1) = N and (M+1)y + 0.5*M*(M+1) = N

Then we can write:

Mx + 0.5*M*(M-1) = (M+1)y + 0.5*M*(M+1)

Solving which, gives us:

Mx(i) = (M+1)y(i) + M

Starting with x(0)=N and M=1, we increment the counter by 1 if y(0) comes out to be an integer. For the next iteration, M=2 and x(1) = y(0) and so on. Repeat this until Mx-M > 0.

We add 1 to the final count because the counter is incremented for each consecutive pair, so if there are P consecutive pairs, then the number of consecutive elements is P+1. The python code is as follows.

import math
class Solution(object):
    def consecutiveNumbersSum(self, N):
        start, m, cnt = N, 1, 0
        while start-m > 0:
            u = start-m
            if u % (m+1) == 0:
                cnt += 1
            start = u
            m += 1
        return cnt+1


Tags: , , , ,

Leave a Reply