CareerCup

quadratic equation?

sigma _(k=1~n) k = (1/2)*n*(n+1)
(1/2)*n*(n+1) = x
n^2 + n - 2x = 0
n = (-1 +_ sqrt(1+8x) ) / 2

will these integers be compulsorily from 2 to n or say 4 to n or 5 to n??

return n.isInteger?();

sigma _(k=2~n) k = (1/2)*n(n+1)-1
(1/2)*n*(n+1)=x-1
n^2+n-2x+1 = 0
n = (-1 +_ sqrt(8x-3))/2

return n.isInteger?()

I understood as this. For N = 12, k = 3 starting from 3, i. e 12 = 3+4+5.

The question also doesn't specify if it is necessary to find the max sequence length. Otherwise for all odd numbers the answer is YES because two consecutive integers that are twice less then the will always result that number, e.g. 13 = 6+7, 17=8+9, 323=161+162. So the question really comes to even numbers. I wonder if just dividing by 3 will help. Let's see:
Consider 14: 14/3=4; let's try 4 as a middle element: 3+4+5=12 - no, too small; let's try 3 as most left one: 4+5+6=15 - no, too large. Hmmm... How about now dividing by 4 and taking 4 elements: 14 / 4 = 3, 2+3+4+5=14. Bingo! The process of increasing the divisor should go up to N/2. That's just an idea.

I think it can be proved that any number can be a sume of consecutive numbers

Assume starting point is s+1 and that given number N can be written as s+1 + s+2 + ... + s+k.

Given an s, we can find k by either solving the quadratic (boring! + precision issues) or just doing a binary search by guessing k and increasing or decreasing the estimate for k.

So take s=1,2,...n-1 and guess k for each such s.

So total time is O(nlogn).

The sum of a series of consecutive numbers is, if N is even, sum = (2*k+1)*N/2; and if N is odd, sum = k*N. k can be any integer depending on the consecutive numbers chosen. So, finally the problem boils down to determine whether the given sum has any number between 2 and n as its divisor.

hiremath[dot]in[slash]2009[slash]10[slash]03

if input is odd number, then return true as long as it is >=5

if input is even:
let's first find the min odd factor: oddmin, oddmin must be at least 3;
let's then find the largest odd factor: oddmax

in case of input number = 2^i, oddmin and oddmax don't exist then return false;
otherwise:
return oddmin/2 <= N/oddmin - 2 || oddmax/2 >= N/oddmax + 1

boolean detSum(int x,int n)
{
if ((x-1)/2 > 1) and ((x-1)/2+1 < n+1)
return true;
else
return false;
}

As long as this number is not 2^i, return true. So use binary form to count consecutive 1s.

the problem as look to me is we have to find consecutive numbers from
2,3,4,5..............N such that they add upto N.
Now have a

low_sum = 1
high_sum = 0;
i = 2 , j = N - 1

while(i<j)
{
sum = j(j+1)/2 - low_sum;

if(sum > N)
j--;
else
{
low_sum +=i;
i++;
}

}

if(i<j)
return true;
else
return false;

for( i = 2; i <= 6; i++){
                sum = i;
                for(j = i+1; j <= 6; j++){
                        if(sum > num)
                                continue;
                        sum+=j;
                        if(sum == num){
                                cout << "Found" << endl;
                                break;
                        }
                }
        }

I assumed N=6 in above example!!

while(i<(n/2)+1)
{

sum +=i;
if (sum==n)
{
break;
}
if(sum > n)
{
sum = sum - j;
j++;
}
if (sum==n)
{
break;
}
i++;
}

Basic Idea is if a number N is sum of consecutive number then

N = Sum of Consecutive number of x - sum of consecutive number of y;
x range from 1 to n ;
y range from 0 to n;

N = x(x+1)/2  - y(y+1)/2

on solving 2N = (x-y)(x+y-1)

Now find firstFactor = x-y
and secondFactor     = x+y-1

x = (firstFactor+secondFactor+1)/2
if x is integer then Y must be integer so return true
else check for other factors
we have to iterate from 1 to root(2N) to find firstfactor and secondfactor 
 

public static boolean isCSum(int n)
{
        while(i=1;i<Math.sqr(2*n);i++)
        {
            int firstTerm  =  i;
            int secondTerm ;
            if((2*n)%i==0)
            { 
                secondTerm=(2*n)/i;
                if((firstTerm+secondTerm+1)%2==0)
                {
                    return true;
                }
            }  
        }
       return false;
}

An integer K can be expressed as a sum of (more than 1)
consecutive positive integers , K != 2^m, where m is an integer.

Its is as simple subset sum problem.
Given array is
2,3,4,5,6,7,8,9.....n

Let given sum be S

Now change the array to
a[j]=a[j]+a[j-1];

So the new array becomes
2,5,9,14,20,27,.... O(n) time complexity

Now make a hashtable with array value as key and index as value.
eg h.put(new Integer(a[j]),new Integer(j)); O(n) space and O(n) time

now do the following
for(i=1;<N;i++)
{
Integer j=h.get(new Integer(Sum-a[i]));
if(j!=Null)
{
System.out.println("Sequence starts at"+j.IntValue()+1,"Sequence ends at "+ i);
break;
}
O(n) time and space complexity solution