Ways To Express

Hard
0/120
Average time to solve is 15m
24 upvotes
Asked in companies
Goldman SachsVisaDeutsche Bank

Problem statement

You are given the number ‘N’. The task is to find the number of ways to represent ‘N’ as a sum of two or more consecutive natural numbers.

Example: 
N = 9
‘9’ can be represented as:
2 + 3 + 4 = 9
4 + 5 = 9
The number of ways to represent ‘9’ as a sum of consecutive natural numbers is ‘2’. So, the answer is ‘2’.
Note: 
1. The numbers used to represent ‘N’ should be natural numbers (Integers greater than equal to 1).
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

The first line and only line of each test case contain a single integer ‘N’, where ‘N’ is the given number.
Output format: 
For every test case, print a single line containing a single integer denoting the number of ways to represent ‘N’ as a sum of two or more consecutive natural numbers. 

The output of each case will be printed in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 1000
3 <= N <= 10 ^ 5

Where ‘T’ is the number of test cases, and ‘N’ is the given number.

Time limit: 1 second

Sample Input 1:

2
21
15

Sample Output 1:

3
3

Explanation Of Sample Input 1:

Test Case 1:

‘21’ can be represented as:
1 + 2 + 3 + 4 + 5 + 6 = 21
6 + 7 + 8 = 21
10 + 11 = 21
The number of ways to represent ‘21’ as a sum of consecutive natural numbers is ‘3’. So, the answer is ‘3’.

Test Case 2:

‘15’ can be represented as:
1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
The number of ways to represent ‘15’ as a sum of consecutive natural numbers is ‘3’. So, the answer is ‘3’.

Sample Input 2:

2
18
16

Sample Output 2:

2
0
Hint

Can we solve this problem by using a prefix sum array?

Approaches (3)
Prefix sum

Use a prefix sum array ‘prefixSum’ (with ‘prefixSum[0] = 0’) whose each index ‘i’ stores the sum of ‘i’ consecutive integers starting from ‘1’. The size of this array will be ‘x’. Here, ‘x + (x-1) <= n’,i.e, when the sum of two consecutive numbers becomes greater than ‘n’. To generate ‘prefixSum’ iterate from index ‘i = 1’ and compute ‘prefixSum[i] = prefixSum[i - 1] + i’. Let, ‘count’ is the number of ways to represent ‘n’ as the sum of consecutive numbers. For an index ‘i’ if the value ‘prefixSum[i] - n’ is present in ‘prefixSum[j]’ (at some index ‘j’) then the sum of numbers from ‘j + 1’ to ‘i’ is equal to ‘n’, increase ‘count’ by ‘1’. Also, if ‘prefixSum[i] - n = 0’ (when ‘prefixSum[i] = n’) increase ‘count’ by ‘1’.

 

For example: Let, ‘n = 15’

So ‘2x -1 <= 15’, we get ‘x <= 8’ (Size of ‘prefixSum’ is 8)

‘prefixSum’ = [0, 1, 3, 6, 10, 15, 21, 28, 36]

‘prefixSum[i] - n’ = [-15, -14, -12, -9, -5, 0, 6, 13, 21]

Here, ‘0’, ‘6’, and ‘21’ are present in ‘prefixSum’, so ‘count = 3’. Hence, the answer is ‘3’.

 

So, for each index ‘i’ if the value ‘prefixSum[i] - n’ exists in the ‘prefixSum’ array, increase ‘count’ by ‘1’. We can use a hash map to find if ‘prefixSum[i] - n’ is present in the ‘prefixSum’ array.

 

Algorithm:

  • Create a hash map ‘prefixMap’. Use it to store the prefix sums. Initially ‘prefixMap’ contains a single value ‘0’.
  • Initialize an integer ‘count = 0’ and ‘prefixSum = 0’. Use ‘count’ to count the number of ways to represent ‘n’ as the sum of consecutive numbers and ‘prefixSum’ to store the prefix sum at index ‘i’.
  • Run a loop where ‘i’ ranges from ‘1’ to ‘x’, here ‘x = (n+1)/2’:
    • ‘prefixSum = prefixSum + i’.
    • Insert the value of ‘prefixSum’ in ‘prefixMap’.
    • If ‘prefixMap’ contains ‘prefixSum - n’, then:
      • ‘count++’
  • Return ‘count’ as the answer.
Time Complexity

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

 

We run a single loop for ‘X iterations. In each iteration, we insert a new element and search for an element in ‘prefixMap’, both of which require ‘O(1)’ time. So, the total time complexity is ‘O(X)’. As ‘X = (N + 1 ) / 2’.  the time complexity is ‘O(N)’.

Space Complexity

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

 

The hash map ‘prefixMap’ contains ‘X’ elements and ‘X = (N + 1 ) / 2’. Thus the space complexity is ‘O(N)’.

Code Solution
(100% EXP penalty)
Ways To Express
Full screen
Console