IIT-D Interview Question for Students


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 1 vote

c# implementation, very quick algorithm.
Complexity: O(c), where c is a constant, which can be calculated as follows:
c = n*2 + (n-1)*2 + (n-2)*2 + ... + 2, where n is a resulting number of summands.
For n = 8, c = 68.
For n = 2, c = 2.

using System;

namespace SumOfConsecutiveIntegers {

    class Program {

        // tihs ShiftVector is for maximum up to 22 summands, but it is quite with reserve, because the real practical number of summands is up to 8
        private static readonly int[] ShiftVector = { 0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10 };

        private static string Sum( int integer ) {
            
            // for all the integers which are power of 2 - impossible
            if ( (integer & (integer - 1) ) == 0) { return "IMPOSSIBLE"; }

            var startVal = _getStartVal( integer, 2 );

            var res = _sum( integer, startVal, startVal + 1 );

            var str = string.Empty;

            for ( int i = 0; i < res.Length; i++ ) {
                str += res[ i ] + " + ";
            }

            return $"{integer} = {str.TrimEnd(" + ".ToCharArray())}";
        }

        private static int[] _sum( int integer, params int[] arr ) {

            int sum = 0;

            for ( int i = 0; i < arr.Length; i++ ) {
                sum += arr[ i ];
            }

            if ( sum == integer ) { return arr; }

            var startVal = _getStartVal( integer, arr.Length + 1 );

            Array.Resize( ref arr, arr.Length + 1 );

            for ( int i = 0; i < arr.Length; i++ ) {
                arr[ i ] = startVal + i;
            }

            return _sum( integer, arr );
        }

        private static int _getStartVal( int integer, int arrLength ) {
            return integer / arrLength - ShiftVector[ arrLength - 1 ];
        }

        static void Main(string[] args) {

            Console.WriteLine("To exit type \"exit\"");
            while (true) {

                var input = Console.ReadLine();
                try {
                    if ( input.ToLower().Equals("exit") ) {
                        break;
                    }
                    var integer = int.Parse( input );
                    if ( integer <= 0 ) {
                        Console.WriteLine( "Don't be naughty! Only positive integers are permitted!" );
                    } else {
                        Console.WriteLine( Sum( integer ) );
                    }
                }
                catch (FormatException) {
                    Console.WriteLine( "Don't be naughty! Only numbers are permitted!" );
                }
            }
        }
    }
}

- zr.roman November 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The solution wouldn't work though if you were allowed numbers larger than 109 plus there's the issue of blowing up the stack for large sum values.

- famish99 November 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

famish99, what do you mean by "The solution wouldn't work though if you were allowed numbers larger than 109" ? I didn't quite catch your idea. My solution allows all integer numbers. You can test yourself.
Also, what do you mean by "the issue of blowing up the stack for large sum values" ? I tested my solution with input integer that is Int32.MaxValue (2147483647). The result was: 2147483647 = 1073741823 + 1073741824.
All the three integers need 12 bytes of memory! 12 bytes! Where is blowing up the stack ??

- zr.roman November 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I should have said it wouldn't work for numbers where large number of consecutive numbers were required to reach the sum. While in practice that may not be required but if the problem asked you to find instances where the list needed to be 10k large you could get into issues with relying on recursion and the hard-coded shift array. If there is an iterative solution available, why not take it?

- famish99 November 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Now I've caught your idea. Thank you for explanation!
First, let me say that I totally rely on the task. It is written there: "the smallest possible number of summands". And my solution reaches this aim. I think, you will agree, that "the biggest possible number of summands" is totally different story, and in that case the solution will be absolutely different.
But nevertheless, I find you notice quite positive, which can lead to some improvements to my code.
1) hard-coded shift array. Really, I made it hard-coded, because the input values according to the task are limited by 109. And the maximal number of summands belongs to 104 (13 summands).
But it is not a problem, below I provide the calculation of shift values (with caching) without hard-coding. So, it will work on the whole range 0..Int32.MaxValue.
2) stack overflow is a real problem when we deal with a huge number of summands. That's true, and I agree totally (once again, I didn't understand your first notice, because I tried to link it to the initial task).
So, I tested my solution on the range 2kkk..Int32.MaxValue, and I got StackOverflowException. It is because with the input numbers which are near to Int32.MaxValue we can get the result of app. 65.000 summands!
But this is also not a problem, below I provide iterative variant of my solution.
(but once again: the solution will not find the biggest possible number of summands, but only will work on the range that is greater than 109, actually it will work on the whole range 0..Int32.MaxValue).
So, your comment exceeds the initial task requirements, but it is still positive because it encourages to think about general programming issues. Thank you for the discussion.

The improvements:

private static int[] _sum(int integer, params int[] arr) {

           //1. iteration instead of recursion
            while (true) {

                int sum = 0;

                for ( int i = 0; i < arr.Length; i++ ) {
                    sum += arr[i];
                }

                if ( sum == integer ) {
                    return arr;
                }

                var startVal = _getStartVal(integer, arr.Length + 1);

                Array.Resize(ref arr, arr.Length + 1);

                for ( int i = 0; i < arr.Length; i++ ) {
                    arr[i] = startVal + i;
                }
            }
        }

        private static int _getStartVal( int integer, int arrLength ) {
            return integer / arrLength - _getShiftValue( arrLength - 1 );
        }

        private static readonly Dictionary<int, int> Dic = new Dictionary<int, int>();
        
        // 2. Calculation instead of hard-coding
        private static int _getShiftValue( int v ) {
           
            int shiftValue;
            if ( Dic.TryGetValue( v, out shiftValue ) ) {
                return shiftValue;
            }

            shiftValue = 0;
            int t = 0;
            for( int i = 0; i < v; i++ ) {
                t++;
                if ( t == 2 ) {
                    shiftValue++;
                    t = 0;
                }
            }
            Dic.Add( v, shiftValue );
            return shiftValue;
        }

- zr.roman November 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

One confusion "express it as the sum of at least two consecutive positive integers" with word "two". It's "all" or "two" consecutive number? Assuming "all" consecutive number.

Can we think of AP series, S = n/2(2a+(n-1)) where "a" and "S" is known so we need to whether a solution exists for a given "a". Now the question, what would be the logic to find initial value "a" to get optimum solution?

I think let's start with a=S/2, S/4, .......

What you think you guys?

- DJ November 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

/* 
en.wikipedia.org/wiki/Arithmetic_progression
x = na + n*( n - 1 )/2 
examples :
  x = 6 
  a = 1 , n = 3 
  6 = 1*3 + 3*(3-1)(3-2)/2  
  x = 10 
  a = 1, n = 4 
  10 = 1 * 4 + (4 -1)(4)/2 
Thus in ZoomBA :: We have this identity 
*/
def find_ap( x ){
  upto = ciel ( x ** 0.5 )
  solved = join ( [1 : upto + 1 ] , [ 2 : upto + 1 ] ) :: {
     a = $.o.0 ; n = $.o.1 
     break ( n * ( a + ( n - 1 )/ 2.0  ) == x ) {
        printf ( 'a :%d, n: %d\n', a , n ) 
        [ a , n ]
     }
  } 
  if ( empty(solved) ){ println('Impossible' ) } 
}
find_ap( 10 )

- NoOne October 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The trick to this problem is recognizing that for a possible solution, given a list of consecutive numbers, the mean must equal the median.

Such as in 24 = 7 + 8 + 9, since the three values average out to 8, if you do a search where 24 / 3 = 8, you know you need 3 values where the mean and median is 8, so 7, 8 and 9.

The obvious solution would be to stop dividing when you reach the sum value, but to save operations, you can also stop dividing when the half of the divider (i.e. half the numbers needed for the list) is greater than the quotient. (Basically if you need 7 numbers to the left of the median but the result of the median is 6, you can't make the list because it requires all natural numbers)

The real meat of this problem is just coming up with the list, so I'll avoid all the tedious bits about getting output from the console.

Code is in python 2, but would work for python 3 if you change the print statement, the division types are correct for both syntaxes

def print_list(sum):
    num_list = get_list(sum)
    if num_list is None:
        print "IMPOSSIBLE"
        return
    print "%d = %s " % (sum, ' + '.join([str(i) for i in num_list]))

def get_list(sum):
    divisor = 2
    while (divisor / 2.0 < 1.0 * sum / divisor):
        return_list = [i for i in range(
            int((1.0 * sum / divisor) - (divisor / 2.0)) + 1,
            int((1.0 * sum / divisor) + (divisor / 2.0)) + 1)] # generate list of consecutive numbers
        list_length = len(return_list)
        median = sum // divisor # using floor division, not a comment
        if list_length % 2 == 0 and return_list[(list_length >> 1) - 1] == median:
            return return_list
        elif list_length % 2 == 1 and return_list[list_length >> 1)] == median:
            return return_list
        divisor += 1
    return None

- famish99 November 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I tried to run your code on ideone.com, and it said there was a mistake in 18 line (elif list_length % 2 == 1 and return_list[list_length >> 1)] == median:),
Maybe, some additions to code are necessary before running. I'm not specialist at python. Can you provide code which can be executed as is on ideone.com?

- zr.roman November 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ConsequitiveSum {
	public static void main(String[] args){
		int num = 8;
		int start = num/2;
		int sum = 0;
		while (start > 0){
			StringBuilder result = new StringBuilder();
			int counter = start;
			while (sum < num && counter > 0){
				sum += counter;
				result.append(counter + "+");
				counter--;	
			}
			if (sum == num){
				String resStr = result.toString();
				System.out.println(resStr.substring(0, resStr.length() - 1));
				return;
			}
			else{
				start--;
				sum = 0;
			}
		}
		System.out.println("IMPOSSIBLE");
	}

}

- mariash November 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public String find (int sum){
		int n = sum/2 ;		
		int tail = 1 ;			
		int min = Integer.MAX_VALUE ;
		int preSum = 0 ;
		String s = "" ;
		for (int i = 1 ; i <= n ; ++i) {
			preSum += i;
			while (preSum > sum) {				
				preSum -= tail ;
				tail++;
			}
			if (preSum == sum) {
				if (i - tail + 1 < min) {
					min = i - tail + 1 ;
					s = getResult (tail, i, sum);
				}
			}
		}
		return min == Integer.MAX_VALUE ? "IMPOSSIBLE" : s;
	}
	
	private String getResult(int s, int e, int sum){
		StringBuilder sb = new StringBuilder();
		for (int i = s ; i <= e ; ++i) {
			sb.append(i) ;
			sb.append("+") ;
		}
		sb.setLength(sb.length() - 1) ;
		sb.insert(0, sum + " = ") ;
		return sb.toString() ;

}

- Scott November 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hello

- Debasis Jana November 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hello?

- Debasis Jana November 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have confusion "express it as the sum of at least two consecutive positive integers" with phrase "at least two". Assuming the word "all".

Can we think of something AP series, S = n/2(2a+(n-1)) where S and "a" is known. Now we need to find whether a validation solution of "n" is exists for a given "a". Now how we will select the value of "a" to get optimum solution?

what you think guys?

- debasis.jana.iit November 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static List<int> GenerateSums(int number)
{
List<int> result = null;
int pCount = 1;
while (pCount++ != number / 2)
{
var median = number / pCount;
var currentResult = new List<int>();
currentResult.Add(median);
var remaining = number - median;
// populate data around median
int k = 0;
while (remaining > 0 && ++k > 0)
{
if (remaining < median && median > k)
{
currentResult.Insert(0, median - k);
remaining -= median - k;
}
if (remaining < 2 * median)
{
currentResult.Insert(currentResult.Count, median + k);
remaining -= median + k;
}
else
{
if (median > k)
{
currentResult.Insert(0, median - k);
}
currentResult.Insert(currentResult.Count, median + k);
remaining -= 2 * median;
}
if (remaining == 0 && currentResult.Count > 1)
{
//Console.WriteLine(string.Join(" = ", number, string.Join(" + ", result)));
result = currentResult;
}
}
//Console.WriteLine("pCount = {0} Median {1} Remaining = {2} Impossible", pCount, median, remaining);
}
Console.WriteLine(string.Join(" = ", number, string.Join(" + ", result)));
return result;
}

- ankushbindlish November 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static List<int> GenerateSums(int number)
        {
            List<int> result = null;
            int pCount = 1;
            while (pCount++ != number / 2)
            {
                var median = number / pCount;
                var currentResult = new List<int>();
                currentResult.Add(median);
                var remaining = number - median;
                // populate data around median
                int k = 0;
                while (remaining > 0 && ++k > 0)
                {
                    if (remaining < median && median > k)
                    {
                        currentResult.Insert(0, median - k);
                        remaining -= median - k;
                    }
                    if (remaining < 2 * median)
                    {
                        currentResult.Insert(currentResult.Count, median + k);
                        remaining -= median + k;
                    }
                    else
                    {
                        if (median > k)
                        {
                            currentResult.Insert(0, median - k);
                        }
                        currentResult.Insert(currentResult.Count, median + k);
                        remaining -= 2 * median;                        
                    }
                    if (remaining == 0 && currentResult.Count > 1)
                    {
                        //Console.WriteLine(string.Join(" = ", number, string.Join(" + ", result)));
                        result = currentResult;
                    }
                }
                //Console.WriteLine("pCount = {0}  Median {1} Remaining = {2} Impossible", pCount, median, remaining);
            }
            Console.WriteLine(string.Join(" = ", number, string.Join(" + ", result)));
            return result;
        }

- ankushbindlish November 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Given a number X, split it into at least two consecutive
        // numbers that sum to X.
        // So 10 = 1 + 2 + 3 +4
        // Find the least number of summands.
        final int N = 34;
        
        //algo:
        // We try from 2 summands and go from there.
        // so if N = a + (a+1), then a = (N - 1)/2 check if this works out. (For all odd numbers this will be best)
        // if N = a + (a+1) + (a+2), then we see a = (N - 3)/3
        // if N = a + (a+1) + (a+2) + (a+3), then we see a = (N - 6)/4
        // So essentially the subtraction value goes up like 1, 1+2, 1+2+3 ... = x(x+1)/2.
        // So we start from x = 1 and try until we have a > 0.
        
        int x = 1;
        boolean found = false;
        while (true) {
            final int sub = x * (x+1) / 2;
            if(sub > N) {
                break;
            }
            int a = (N - sub) / (x+1);
            if(a * (x+1) + sub == N) {
                //found it!
                System.out.println("Found sum for N: " + N);
                for(int i = 0; i <= x; i++) {
                    System.out.println(a + i);
                }
                found = true;
                break;
            }
            x++;
        }
        if (!found) {
            System.out.println("Sum impossible for N: " + N);
        }

- MongoLikeCode November 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h> 
#include <stdlib.h> 



int consnums(int);

int consnums(int m)
{

	int sum =0;
	int i,j, k = 0, flag = 1;  

	for(i=1; flag && i<110; i++) {

		 sum = 0; 
		 flag = 1; 
		 j = k++; 

		for(j=k; sum < m && j<110; j++){
			sum += j; 

		}
		if (sum == m){
			flag = 0;
		}
	}

	if(flag)
		printf("IMPOSSIBLE\n");
	else 
		printf("FOUND THE RANGE %d and %d\n", k, j-1);
	
	return 0;			
}


int main(int argc, char const *argv[])
{
	/* code */
	int i=0;
	for (int i = 1; i < 300; ++i)
	 {
	 	printf("%d\t", i);
		consnums(i);
		printf("\n");

	 } 

	return 0;
}

- Braveheart November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>



int consnums(int);

int consnums(int m)
{

int sum =0;
int i,j, k = 0, flag = 1;

for(i=1; flag && i<110; i++) {

sum = 0;
flag = 1;
j = k++;

for(j=k; sum < m && j<110; j++){
sum += j;

}
if (sum == m){
flag = 0;
}
}

if(flag)
printf("IMPOSSIBLE\n");
else
printf("FOUND THE RANGE %d and %d\n", k, j-1);

return 0;
}


int main(int argc, char const *argv[])
{
/* code */
int i=0;
for (int i = 1; i < 300; ++i)
{
printf("%d\t", i);
consnums(i);
printf("\n");

}

return 0;
}

- Braveheart November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h> 
#include <stdlib.h> 



int consnums(int);

int consnums(int m)
{

	int sum =0;
	int i,j, k = 0, flag = 1;  

	for(i=1; flag && i<110; i++) {

		 sum = 0; 
		 flag = 1; 
		 j = k++; 

		for(j=k; sum < m && j<110; j++){
			sum += j; 

		}
		if (sum == m){
			flag = 0;
		}
	}

	if(flag)
		printf("IMPOSSIBLE\n");
	else 
		printf("FOUND THE RANGE %d and %d\n", k, j-1);
	
	return 0;			
}


int main(int argc, char const *argv[])
{
	/* code */
	int i=0;
	for (int i = 1; i < 300; ++i)
	 {
	 	printf("%d\t", i);
		consnums(i);
		printf("\n");

	 } 

	return 0;
}

- Braveheart November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//
// main.c
// InterviewQuestion-ConsecutiveSum
//
// Created by You In Sun on 2015. 11. 27..
// Copyright © 2015년 You In Sun. All rights reserved.
//

#include <stdio.h>

int main(int argc, const char * argv[])
{
int n[10];
int t;
int cnt1 = 0;
int cnt2 = 0;

// insert code here...
printf("Hello, World!\n");

scanf("%d", &t);

for(cnt1=0; cnt1<t; cnt1++)
scanf("%d", &n[cnt1]);

for(cnt1=0; cnt1<t; cnt1++)
{
int a = 0;
int i = 1;
int j = 0;
int flag = 0;
int ini = 0;
int con = 0;



while(1)
{
while(1)
{
a = a + (i + (j++));
if( n[cnt1] == a )
{
flag = 1;
ini = i;
con = j;
//printf("\n");
break;
}
if( n[cnt1] < a )
break;

}

if(j>=3)
{
i++;
j = 0;
a = 0;
}
else
{
if(flag == 1)
{
// select minimum summand;
printf("\r\n %d =", n[cnt1]);
for(cnt2=0; cnt2<con; cnt2++)
{
if(cnt2 != 0)
printf(" +");
printf(" %d ", ini+cnt2);

}
}
else
printf("\r\n IMPOSSIBLE");
break;
}
}
}
printf("\n");
return 0;
}

- Anonymous November 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
int powerof2(int);


int main()
{
int num,endindex,k,sum=0;
int array[55],i,i1,j=0;
int check;
printf("enter the number between 1 and 109 :=>");
scanf("%d",&num);

check =powerof2(num);
if(check==0)
printf("IMPOSSIBLE");
else
{

if(num%2>0)
{
++num;
num=num/2;
printf("%d %d ",num,num-1);
}


else
{
for(i=0;i<num/2;i++)
{
array[i]=++j;
//printf("%d",array[i]);
}




endindex=i;
k=i;
while(1)
{
sum=sum+array[k--];

if(sum>num)
{
endindex--;
k=endindex;
sum=0;
}

if(sum==num)
break;

}

for(i1=++k;i1<=endindex;i1++)
printf(" %d ->",array[i1]);

}

}


return 0;


}



int powerof2(int num)
{
int i=2;
while(i<num)
{
i=i*2;
}

if(i==num)
return 0;
else
return 1;
}

- mithleshtechno December 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i, num, cases;
    printf("enter the number of cases");
    scanf("%d", &cases);
    for(i=0; i<cases; i++)
    {
    printf("\nenter the number");
    scanf("%d", &num);
    FindNum(num);
    }
    return 0;
}

void FindNum(int num)
{
    int x, y;
    for(x=1; x<num; x++)
    {
        for(y=0; y<x; y++)
        {
            if(2*num==(x-y)*(x+y+1))
            {
                PrintSum(num, x, y+1);
                return;
            }
        }
    }
    printf("\nIMOSSIBLE");
    return;
}

void PrintSum(int num, int x, int y)
{
    printf("\n%d=%d", num, x);
    x--;
    while(x>=y)
    {
        printf("+%d", x);
        x--;
    }
}

- Sandeep Chauhan December 29, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More