## 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!" );
}
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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 ??

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

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

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?

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

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

Comment hidden because of low score. Click to expand.
0

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?

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");
}

}``````

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

}

Comment hidden because of low score. Click to expand.
0

Hello

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

Hello?

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?

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>();
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;
}

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>();
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;
}``````

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

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

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

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

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

#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;
}

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

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

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.

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