IIT-D Interview Question
StudentsCountry: India
Interview Type: In-Person
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, 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 ??
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?
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;
}
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?
/*
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 )
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
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?
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");
}
}
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() ;
}
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?
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;
}
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;
}
// 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);
}
#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;
}
#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;
}
#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;
}
//
// 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;
}
#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;
}
#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--;
}
}
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.
- zr.roman November 14, 2015