CareerCup

Can be solved in O(N) using window sliding.

Just sum 1 + 2+ 3.. etc and if sum of first i numbers gets bigger than N (using right pointer), then just move left pointer and substract as long as you don't get one solution. when you get a solution, increment both pointers.

(k+1)*a + k(k+1)/2 = N
N = (k+1)(a + k/2)
2N = (k+1)(2a+k)

Then, for N not-too-big, we can use integer factorization to find all pairs (a,k).
Just find all pairs (u,v) that u*v = 2N, considering all positive and negative divisors, then k = u-1, a = (v-k)/2. Of course, v-k must be even, otherwise ignore them.

If a, k are integers, then N must be integer.
If N real, a must be real. But then for any k we can find a. Thus there's not finite #solutions.

Windows sliding

public class sumCons
{

	static int doesSum(int a, int N)
	{
		int sum = a;
		while(sum<N && a>0)
		{
		  sum = sum+(a-1);
		  a--;
		}
		
		if(sum==N)
		{
			return a;
		}
		else
		{
		   return -1;
		}}
	
	public static void main(String args[])
	{
		int X = args[0];
		int b;
		int a = X/2;
		while(a>1)
		{
			b = doesSum(a,X);
			if(b!=-1)
			{
				System.out.println("("+b+","+a+")");
			}
			a--;
		}
}
}

This is a variation on the Sliding Window algorithm without a fixed window size. Code is a bit messy but works. Appreciate comments and feedback
PS: This will print the consecutive sums (not the pair a,k)
Doesn't take into account the -ve numbers or real numbers scenarios.

public class SumOfConsecutives {

	private static List<String> result = new ArrayList<>();
	
	public static List<String> process(int n)
	{
		
		//Corner cases, assumes n is +ve
		if(n < 0)
			result.add("Invalid input");
		if(n == 0)
			result.add("No sums");
		else if(n == 1)
			result.add("0 + 1");
		else if(n == 2)
			result.add("No sums");
		else // >1
		{
			String consecutive = "";
			int sum = 0;
			int start = 0;
			int nextStart = 0;
			//Naive approach
			while(start <= Math.floor(n/2)) //for example: n = 20, start = 10. 
			{
				while(sum < n)
				{
					sum += nextStart;
					consecutive += nextStart + " + ";
					nextStart++;
				}
				if(sum == n)
				{
					result.add(consecutive);
				}
				//reset
				start = start+1;
				nextStart = start;
				consecutive = "";
				sum = 0;
			}
			
		}
	
		return result;
	}
	
}

//For positive numbers.
public void printConsecNums(int n)throws InvalidInputException
{
	if(n<=0)
	{
		throw new InvalidInputException();
	}
	Queue<Integer> consecSums=new LinkedList<Integer>();
	int sum=0;
	for(int i=1;sum<n;i++)
	{
		sum+=i;
		consecSums.enqueue(sum);
	}

	int start=1;
	//if sum is larger then n, try removing values from the queue until you get a value less than or equal to n.
	while(sum>n)
	{
		int top=consecSums.dequeue().intValue();
		sum=sum-top<=n?sum-top:sum;
		start++;
	}
	sum==n?printConsecValues(start,n):System.out.println( n + " cannot be expressed as the sum of consecutive values ");
	
	
}

private void printConsecValues(int s,int target)
{
	int sum=0;
	for(int i=s; i+sum<=target;i++)
	{
		System.out.print(i + " ");
		sum+=i;
	}
}
/**Time complexity is O(m+k) where m is the number of operations needed to get a sum>=n, k is the number of values to be removed from the queue to get the sum
to be less than or equal to n.**/
//For negative integers, we have to change the loops and the start variable (ie. for (int i=-1; sum>n;i--), while (sum<n), start=-1).

private static void getConsecutives(int num) {
// TODO Auto-generated method stub
int sum = 0, i=0, j=0;
for(i=0, j=0; sum != num;)
{


if(sum < num)
{
j++;
System.out.println("sum: " + sum + " adding: " + j);
sum += j;

}
else
{
i++;
System.out.println("sum: " + sum + " subtracting: " + i);

sum -= i;
}
}
System.out.println("The consecutive numbers are: ");
i++;
while(i < j)
{
System.out.print(i + ", ");
i++;
}

System.out.println(j);
}

Based on the sliding window concept, a O(N) solution.
1. Maintain two pointers
2. When SUM is equal to given N, then print the range and increment both the pointers.

public static void slidingWindow(int n){
		int ptr1=1;
		int ptr2=1;
		int sum=1;
		while(ptr2 < n/2){
			if(sum>n){
				sum -= ptr1;
				ptr1++;
			}
			else if(sum < n){
				ptr2++;
				sum += ptr2;				
			}
			else{
			sum(ptr1,ptr2);
			sum -= ptr1;
			ptr1++;
			ptr2++;
			sum += ptr2;
			}			
		}
	}
	
	public static void sum(int a, int b){
		StringBuilder sb = new StringBuilder();
		for(int i=a;i<=b;i++){
			sb.append(i);
			if(i != b) sb.append(" + ");
		}
		System.out.println(sb.toString());
	}

#include <stdio.h>
#include <math.h>

// set N input here
double N = 5.0;

int
main(void)
{
	int half;
	int bottom;
	int answers[1024];

	half = 	ceil(N / 2); // note that we dont ever have to sum numbers > ceil(N/2)

	bottom = 1;

	while (bottom < half)
	{
		int i;
		size_t answer_n;
		int sum;

		sum = 0;
		answer_n = 0;

		for (i = bottom; i <= half; i++)
		{
			answers[answer_n++] = i;
			sum = sum + i;
			if (sum == N)
			{
				// found consecutive numbers! print them
				int j;
				for (j = 0; j < answer_n; j++)
				{
					printf("%d ", answers[j]);
				}
				printf("\n");
				break;
			}
		}
		sum = 0;
		bottom++;
	}

	return 0;
}

#include<iostream>

using namespace std;

int main() {
int i=0, n=0, s=0, prev=0, next=0;
cout << " Enter n " ;
cin >> n;

while(i<n)
{
if(s == n) {
cout << " Sum is found for " << prev << " to " << next << endl;
break;
}

while(s > n ) {
s = s - prev;
prev++;
if(s == n)
{
cout << " Sum is found for " << prev << " to " << next << endl;
break;
}
}

if(s == n)
break;
s = s + i;
next = i;
i++;
}
if( s > n)
cout << " Sum for " << n << " not exist " << endl;
return 0;
}

The solution is sqrt(n)

start with sum = 0
then add i=1, 2, 3, 4, ....
at each addition check if n - sum is dividable by i