CareerCup

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

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

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

}

Hello?

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