Count of sum of consecutives
You are given a positive integer 'N.' Your task is to find the number of ways to represent the given number 'N' as the sum of two or more consecutive natural numbers.

Input Format:

The first line contains an integer, ‘T,’ which denotes the number of test cases or queries to be run. Then, the 'T' test cases follow. The first and the only line of each test case contains one integer 'N', as described in the problem statement.

Output Format:

For each test case, return one integer denoting the number of ways to represent the given number 'N' as the sum of 2 or more consecutive natural numbers.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1

Question

Count of sum of consecutives

You are given a positive integer 'N.' Your task is to find the number of ways to represent the given number 'N' as the sum of two or more consecutive natural numbers.

Input Format:

The first line contains an integer, ‘T,’ which denotes the number of test cases or queries to be run. Then, the 'T' test cases follow.

The first and the only line of each test case contains one integer 'N', as described in the problem statement.

Output Format:

For each test case, return one integer denoting the number of ways to represent the given number 'N' as the sum of 2 or more consecutive natural numbers.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 10^8

Time Limit: 1 sec

Accepted Answer

Brute Force Approach

Approach:

In this brute force approach,. We will iterate from 1 to ‘N’ using the iterator i and will check if there is a possible sequence of consecutive positive integers such that their sum is ‘N’, and the ending integer of the consecutive sequence is 'i'. The checking will be done as follows:

We know that the ending position is ‘i’. Therefore, we need to find a starting point for the consecutive sequence. Let that integer is 'k'.
Now we can say that (i*(i+1))/2 - (j*(j+1))/2 = ‘N’, where ‘j’ = ‘k-1’ (since sum of first n natural numbers is given by the equation (N*(N+1))/2).
After simplifying the equation in the above point we will get : (j^2 + j + 2*N - i^2 - i) = 0
Now, if there exists a positive integral root for ‘j’ in the above equation, then there is an answer, and we will count this sequence in our answer, or else it is not possible, then we will not count this sequence in the answer.

Steps:

Create a variable to store the answer (say, ANS) with 'ANS' = 0.
Run a loop from ‘i’ = 0 to ‘N’ and do:
1. Create three variables (say A,B and C) and initialize ‘A’ = 1, ‘B’ = 1 and ‘C’ = 2 * ‘N’ - i * i - i.
2. Create a variable ‘D’ and initialize ‘D’ = B * B - 4*A*C.
3. Create a variable 'SQROOT' and initialize 'SQROOT' = square root of ‘D’.
4. Create a boolean variable ‘CHECK’ initialized with false.
5. If ‘D’ >= 0 and SQROOT * SQROOT == D :
  1. If (-B + SQROOT) is divisible by (2 * A) and (-B + SQROOT) / (2 * A) >= 0 and (i - ((-B + SQROOT) / (2 * A))) >= 2 :
    1. ‘CHECK’ = true
  2. If (-B - SQROOT) is divisible by (2 * A) and (-B - SQROOT) / (2 * A) >= 0 and (i - ((-B - SQROOT) / (2 * A))) >= 2 :
    1. ‘CHECK’ = true
6. If ‘CHECK’ is true:
  1. Increment the ‘ANS’ variable by 1.
Finally, return the ‘ANS’ variable.

Space Complexity: O(1)Explanation:

O(1).

Since constant extra space is required.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the given number.

We are iterating from 1 to ‘N’, and finding the root of the equation takes constant time. Hence, the time complexity is O(N).

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(1),



    Where N is the given number.

'''



import math



def countWays(n):

    ans = 0



    for i in range(1, n):

        a, b = 1, 1

        c = 2*n - i*i - i

        d = b*b - 4*a*c



        sqroot = 0

        if d > 0:

            sqRoot = math.sqrt(d)

            

        check = False



        if d >= 0 and sqRoot**2 == d:

            if ((-b + sqRoot) % (2*a) == 0) and ((-b + sqRoot) / (2*a) >= 0) and ((i-((-b + sqRoot) / (2*a))) >= 2):

                check = True

            if ((-b - sqRoot) % (2*a) == 0) and ((-b - sqRoot) / (2*a) >= 0) and ((i-((-b - sqRoot) / (2*a))) >= 2):

                check = True



        if check == True:

            ans += 1



    return ans

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(1),



    where 'N' is the given number.

*/



public class Solution {

    public static int countWays(int n) {

        // Variable to store the answer.

        int ans = 0;

        for (long i = 1; i < n; i++) {

            long a = 1, b = 1, c = 2 * n - i * i - i, d = b * b - 4 * a * c;

            long sqRoot = (long)Math.sqrt(d);

            boolean check = false;

            // Checking if the equation has a positive integral root. 

            if (d >= 0 && sqRoot * sqRoot == d) {

                if ((-b + sqRoot) % (2 * a) == 0 && (-b + sqRoot) / (2 * a) >= 0 && (i - ((-b + sqRoot) / (2 * a))) >= 2) {

                    check = true;

                }



                if ((-b - sqRoot) % (2 * a) == 0 && (-b - sqRoot) / (2 * a) >= 0 && (i - ((-b - sqRoot) / (2 * a))) >= 2) {

                    check = true;

                }



            }

            

            // If positive integral root exists increment the answer.

            if (check) {

                ans++;

            }



        }

        

        return ans;

    }

}

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space Complexity: O(1),

    where 'N' is the given number.
*/

int countWays(int n) {
    // Variable to store the answer.
    int ans = 0;
    for (long int i = 1; i < n; i++) {
        long int a = 1, b = 1, c = 2 * n - i * i - i, d = b * b - 4 * a * c;
        long int sqRoot = sqrt(d);
        bool check = false;
        // Checking if the equation has a positive integral root. 
        if (d >= 0 && sqRoot * sqRoot == d) {
            if ((-b + sqRoot) % (2 * a) == 0 && (-b + sqRoot) / (2 * a) >= 0 && (i - ((-b + sqRoot) / (2 * a))) >= 2) {
                check = true;
            }

            if ((-b - sqRoot) % (2 * a) == 0 && (-b - sqRoot) / (2 * a) >= 0 && (i - ((-b - sqRoot) / (2 * a))) >= 2) {
                check = true;
            }

        }
        
        // If positive integral root exists increment the answer.
        if (check) {
            ans++;
        }

    }
    
    return ans;
}

Accepted Answer

Efficient Approach