Microsoft Interview Question
Software EngineersCountry: 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.