## Microsoft Interview Question

Software Engineers**Country:**United States

**Interview Type:**In-Person

(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.

```
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;

}

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

- NenadCro January 02, 2016Just 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.