# Interview Questions

# Consecutive numbers with sum equal to n

- February 10, 2018
- Posted by: Kamal Rawat
- Category: Algorithms

Given a positive integer n, print the consecutive numbers whose sum is equal to n. For example,

n = 20 Output: 2, 3, 4, 5, 6 (because 2+3+4+5+6+7 = 20) n = 29 Output: 14, 15

**Solution:**

To see the video solution of this problem, see the below video, else continue reading:

The brute force solution to this problem is to use two nested loops and use all possible start and end points between 1 to n (both inclusive)

void findNumbersBruteForce(int n) { for(int start = 1; start<=n; start++) { for(int end = start; end<=n; end++) { int sum = 0; for(int i=start; i<=end; i++) sum += i; if(sum == n) { // PRINT NUMBERS FROM start TO end for(int i=start; i<=end; i++) cout<<i<<" "; return; } } } }

This function takes O(n^{2}) time. A better solution is to use a sliding window and adjust the start and end as per the below logic:

start = 1 end = 1 sum = 1; // SUM OF ELEMENTS FROM start TO end (both including) while(true) { IF (sum == n) PRINT NUMBERS FROM start TO end AND RETURN ELSE IF (sum < n) end++; // MOVE end FORWARD sum += end; ELSE sum -= start; // MOVE start FORWARD start++; }

The while loop is not an infinite loop because the solution exist for all numbers (in the worst case, start=end=n is the solution).

void findNumbers(unsigned int n) { int start = 1; int end = 1; int sum = 1; while(1) { if(sum == n) { // PRINT NUMBERS FROM start TO end while(start <= end) { cout<< start<<" "; start++; } return; } else if(sum<n) { end++; sum += end; } else { sum -= start; start++; } } }

This code takes O(n) time because in each iteration we are moving either start or end forward. In the worst case, the loop may iterate 2*n times before both start and end becomes more than n itself.