Express as Consecutive Number Sum

Time: O(1)

Space: O(1)

Intuition

A positive integer can be expressed as a sum of consecutive integers iff it is not a power of 2. This follows from number theory: if k >= 2 consecutive integers starting at a sum to n, then n = k*(2a+k-1)/2 = k*(a + (k-1)/2). For this to have an integer solution, n must not be purely a power of 2. The bitwise check n & (n-1) != 0 determines if n has more than one bit set.

Algorithm

1Use the bitwise property: a power of 2 has exactly one bit set.
2If n & (n-1) == 0, then n is a power of 2 (including n=1), so return false.
3Otherwise, n is not a power of 2, so return true.

Example Walkthrough

Input: n = 15

1.n = 15 = 0b1111 (four bits set).
2.n & (n-1) = 15 & 14 = 0b1111 & 0b1110 = 0b1110 = 14 != 0.
3.So 15 is not a power of 2, return true.
4.15 can be expressed as 7+8 (consecutive) or 4+5+6 or 1+2+3+4+5.

Output: true

Common Pitfalls

•The number 1 is a special case: it is 2^0, so it cannot be expressed as a sum of k>=2 consecutive integers. n & (n-1) correctly returns 0 for n=1.
•The bitwise trick is correct only because of the mathematical relationship between powers of 2 and consecutive-sum expressibility.
•This solution assumes n >= 1; negative or zero inputs would need separate handling.

Express as Consecutive Number Sum.java

Java


// Approach: Bitwise check. A number can be expressed as sum of consecutive integers iff it is NOT a power of 2.
// This follows from the formula: sum of k consecutive integers starting at a is k*(2a+k-1)/2.
// For this to equal n, n must not be divisible only by powers of 2. Use bitwise trick: n & (n-1) != 0.
// Time: O(1) Space: O(1)

class Solution {

    public boolean isSumOfConsecutive(int n) {
        return (n & (n - 1)) != 0;
    }
}

Was this solution helpful?