Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Problem:
1.1.
Example -
2.
Naive Approach
2.1.
Implementation
2.1.1.
Output
2.1.2.
Time Complexity: O(NlogN)
2.1.3.
Space Complexity: O(1)
3.
Efficient Approach
3.1.
Implementation
3.1.1.
Output:
3.1.2.
Time Complexity: O(sqrt(N) * log(N))
3.1.3.
Space Complexity: O(1)
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Number Of Ways To Get A Sum Equal To N Using Odd Consecutive Natural Numbers

## Problem:

Given a number N (1 <= N <= 10 ^ 9), find the number of ways to get a sum equal to N by adding consecutive odd numbers.

Note: Consecutive odd numbers are the set of numbers where each number is not divisible by 2, and the difference between any two consecutive numbers is 2. For eg: [1, 3, 5], [15, 17, 19, 21] are valid sets and [3, 7, 9], [2, 3, 5] are not valid.

### Example -

Input: N = 63

Output: 3

Explanation: There are three sets of consecutive odd natural numbers that give sum = 63:

1. [3, 5, 7, 9, 11, 13, 15]
2. [19, 21, 23]
3. [63]

Therefore, the number of ways to get a sum equal to N is 3.

Input: N = 9

Output: 2

Explanation:

The valid sets of consecutive odd natural numbers are:

1. [1, 3, 5]
2. [9]

Therefore, the number of ways to get a sum equal to N is 2.

Also see, Euclid GCD Algorithm

## Naive Approach

Let us call the endpoints of the set of consecutive odd numbers L and R, where ‘L’ is the left endpoint and ‘R’ is the right endpoint. Now we have to check if the sum of odd consecutive numbers between ‘L’ and ‘R’ (inclusive) is equal to the ‘N’ or not. Note that both ‘L’ and ‘R’ will be odd.

Recall the basic mathematical formula - the sum of the first ‘X’ odd natural numbers is X ^ 2. We can use this formula to find the sum of natural numbers between ‘L’ and ‘R’ as follows:

``````The number of odd numbers < L = floor(L / 2)
The number of odd numbers <= R = ceil(R / 2)
The sum of odd numbers that are < L = (floor(L / 2)) ^ 2
The sum of odd numbers that are <= R = (ceil(R / 2)) ^ 2
The sum of odd numbers between L and R = ceil(R / 2) ^ 2 - floor(L / 2) ^ 2``````

Using the above formula, we can now calculate the sum of all the odd numbers between L and R in constant time. Now we can iterate over both the endpoints - L and R and check if the sum of odd numbers between L and R equals N, then increment our answer. In the end, we will get the number of ways to get a sum equal to N.

Can we do any further optimization in this approach? Obviously Yes. We are smart. We can do it. Note that for a fix L, the sum of the odd numbers will always increase as R increases. It means that first for some values of R, the sum will be less than N, then it may become equal to N, and later it will become greater than N. This gives us the idea to use a Binary Search. We can binary search over the right endpoint R.

### Implementation

``````#include<bits/stdc++.h>
#define ll long long
using namespace std;

/*
Function to find the
Number of ways to get a sum equal to N.
*/
void solve(int n){
int ans = 0;

// Iterating over the left endpoint
for (int i = 1; i <= n; i+=2){

int l = i;
int r = n;

// Doing Binary Search over right endpoint
while (l <= r){
int mid = (l+r)/2;

// Number of odd numbers < L
int cnt_L = i/2;

// Number of odd numbers <= R
int cnt_R = (mid+1)/2;

// Calculating sum of odd nos from L to R.
int cur_sum = cnt_R*cnt_R - cnt_L*cnt_L;

// If sum = n, increment answer and break.
if (cur_sum == n){
ans++;
break;
}

// If sum < n, increment the left pointer
else if (cur_sum < n){
l = mid+1;
}

// If sum > n, decrement the right pointer
else{
r = mid-1;
}
}
}

// Printing the number of ways to get a sum equal to N.
cout<<ans<<endl;
}

// Driver Code
int main(){
int n = 63;
solve(n);
}``````

#### Output

``3``

#### Time Complexity: O(NlogN)

In the above approach, we are iterating over the left endpoint L from 1 to N and for each L, we are performing a binary search over the right endpoint to find the number of ways to get a sum equal to N. Since we are calculating sum in constant time, each binary search will take O(logN) time. Therefore, the total time complexity of the above approach is O(NlogN).

#### Space Complexity: O(1)

We are just using some extra variables in this approach therefore the space complexity is O(1).

Read More - Time Complexity of Sorting Algorithms

## Efficient Approach

The time-consuming step in our previous approach was iterating over the left endpoint, which took O(N) time. Even if we iterate over the right endpoint and perform a binary search for the left endpoint, the time complexity won’t change.

We need a variable that is smaller than O(N), over which we can iterate. Both L and R are O(N). Which other parameter is variable in this approach? Yes, you guessed it right, the Length of the set of consecutive odd natural numbers. But is it less than O(N)? Let us see.

Let X be the length of the set of consecutive odd natural numbers. The smallest sum that we can form from X consecutive odd natural numbers is X^2 by choosing the first X natural numbers. Therefore, to get a sum of N, the maximum length of the set will be sqrt(N).

Now we can iterate over the length of the set and perform a binary search for the left endpoint. Once the length of the set X and the left endpoint L is fixed, the right endpoint R will automatically get fixed. We can now calculate the sum of odd numbers between L and R using the formula in the previous approach.

### Implementation

``````#include<bits/stdc++.h>
#define ll long long
using namespace std;

/*
Function to find the
Number of ways to get a sum equal to N.
*/
void solve(int n){
int ans = 0;

int sq = sqrt(n)+1;

// Iterating over the length of the set
for (int i = 1; i <= sq; i++){

int l = 0;
int r = n;

// Doing Binary Search over left endpoint
while (l <= r){
int mid = (l+r)/2;

int left = mid;
int right = mid + i;

// Calculating sum of odd numbers.
int cur_sum = right*right - left*left;

// If sum = n, increment answer and break.
if (cur_sum == n){
ans++;
break;
}

// If sum < n, increment the left pointer
else if (cur_sum < n){
l = mid+1;
}

// If sum > n, decrement the right pointer
else{
r = mid-1;
}
}
}

// Prining number of ways to get a sum equal to N.
cout<<ans<<endl;
}

// Driver Code
int main(){
int n = 63;
solve(n);
}``````

#### Output:

``3``

#### Time Complexity: O(sqrt(N) * log(N))

We are iterating over the length of the set and then performing a binary search over the left endpoint. The length of the set is O(sqrt(N)), and the binary search will take O(logN) time. Therefore the time complexity of the above approach is O(sqrt(N) * log(N)).

#### Space Complexity: O(1)

We just used some extra variables that occupy constant space. Therefore the space complexity is O(1).

## FAQs

1. What is the sum of first X odd natural numbers?
The sum of the first X odd natural numbers is X ^ 2.

2. What is Binary Search?
Binary search is an efficient algorithm for finding a particular key from a sorted list of numbers. Instead of iterating over each number, we check for the middle index and eliminate one-half of the list in a single check.

## Key Takeaways

This article discussed finding the number of ways to get a sum equal to N from a set of consecutive odd natural numbers. We also discussed the time and space complexity of our solution. If you want to solve more such problems, you can visit Coding Ninjas Studio.

If you think that this blog helped you share it with your friends!. To be more confident in data structures and algorithms, try out our DS and Algo Course.

Check out this problem - Two Sum Problem

Until then, All the best for your future endeavors, and Keep Coding.

Live masterclass