829. Consecutive Numbers Sum - cocoder39/coco39_LC GitHub Wiki

829. Consecutive Numbers Sum

First idea is O(N) solution

class Solution:
    def consecutiveNumbersSum(self, N: int) -> int:
        sum_i = 0
        visited = set()
        count = 0
        for i in range(N+1):
            sum_i += i
            if sum_i - N in visited:
                count += 1
            visited.add(sum_i)
        return count

Thinking process of O(N^0.5)

N = k + (k+1) + (k+2) + ... + (k+i-1) => N = i*k + (i-1) * i / 2 => N - (i-1) * i / 2 = k * i

i >= 1 because at least one element (i-1) * i is for sure even number so (i-1) * i / 2 is an integer

class Solution:
    def consecutiveNumbersSum(self, N: int) -> int:
        count = 0
        i = 1
        while N > (i-1) * i // 2:
            if (N - (i-1) * i // 2) % i == 0:
                count += 1
            i += 1
        return count