CareerCup

Use Recursion : Pass the value of the range and keep increasing the range

int sum(int i, int j, int[] array)
{
  if( i <=j)
    {
       return array[i] + sum(i+1,j,array);
     }
     else
        return 0;

}

Use a while loop? goto?

Stupid question for an interview.

Use tail recursion. Plain recursion is inefficient and most likely will blow up the stack. The following code allows tail recursion optimization (with option -O2 at least in gcc), try it, it won't blow up.

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

int tailSum(int*buf, int n, int sum) {
    if (n == 0)
        return sum;
    return tailSum(buf + 1, n - 1, sum + buf[0]);
}

int main() {
    int *buf = (int*)malloc(sizeof(int) * 1000000);
    // initialize buf contents
    printf("%d\n", tailSum(buf, 1000000, 0));
    return 0;
}

aaye yaar while loop laga lo, if for loop is not allowed.

This comment has been deleted.

Using recursion :)

private static int sumArray(int a[], int pos) {
		if(pos==a.length)
			return 0;
		return a[pos]+sumArray(a, pos+1);
	}

Int FindTheSum(int x,int y , int a[])
{
if(x==y) // Cover Terminating cases
{
return a[x];
}
if(x<y){
return a[x]+FindTheSum(x+1,y,a);
}
else
throw exception;
}

Tail recursive algorithm.

private long subarraySum( int[] arr, int from, int to, long res ){
		
		if( from > to ){
			throw new IllegalArgumentException("from > to: " + from + " > " + to);
		}
		
		if( from < 0 || from >= arr.length || to >= arr.length ){
			throw new IllegalArgumentException("'from' or 'to' is incorrect");
		}
		
		if( from == to ){
			return res + arr[to];
		}
		
		return subarraySum( arr, from+1, to, res + arr[from] );		
	}

My instinct for this problem is ... interviewer is trying test some wide range of data structure and algorithm that we should know. It obviously needs preprocessing to avoid loop for range sum. This is sum range problem. Cumulutive sum or prefix sum gives us solution in O(n) preprocessing time but O(1) query time. However with segment tree preporcessing it will be <O(log n ) , O(logn)>

#include <functional>
#include <numeric>

long sum(int i, int j, int [] numbers)
{
        return accumulate(numbers,numbers+abs(i-j)+1,0);
}

We can maintain a cumulative array from the begining. Let it be c[].

Then, summation(a[i]...a[j]) will be c[j] - c[i].

Guys, in above solution of mine, last statement is = return n*(n+1) / 2 and not "%"

Use the formula = n(n+1) / 2. Where n = | i - j | + 1.

long Sum(int i, int j)
{
int n = abs(i-j) + 1;
return n*(n+1) % 2;
}