CareerCup

Is subarray has to be contiguous then the following should do

void findsubarray (int arr[])
{
	int length = sizeof(arr)/sizeof(a[0]);
	int A[length];

	int i, j;

	A[0] = arr[0];
	for (i=1;i<length;i++) A[i] = A[i-1] + arr[i];
	
	for (i=0;i<length;i++)
		for (j=i;j<length;j++)
		{
			if ( (arr[i] + A[j]-A[i]) % length) continue;
			else
			{
				//arr[i].......arr[j] is the needed subarray
			}
		}

}

bool IsSubArray(int n, int *arr, int N, Sum) // N is the number of elements in the array
{
if(n < 0)
return false;
if(Sum \ N == 0)
return true;
else
{
return (IsSubArray(n-1, arr, N, Sum + arr[n-1]) | IsSubArray(n-1, arr, N, Sum);
}
}

This fn will find whether there is any subarray like this.
We can easily modify this fn to get the elements of the subarray which has the sum divisible by N

(1) Let N be the array length and create a new array called mod, where mod[i] = (sum of all elements up to index i) % N.
(2) As we build the mod array, look for a previous position j where mod[j] = mod[i]. If such a j exists, then we know the subarray(j+1, i) should have a sum that's divisible by array length. We can use a Hashtable to store this info, or even an array (just need to initialize it first).
(3) By pigeonhole principle, there can be at most N different modulos. Either one of them is 0 or two of them are the same, so we should always have such a subarray.

static int[] subarray(int[] arr) {
    int N = arr.length;
    int mod[] = new int[N];
    HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
    int curr = 0;
    for(int i=0; i<N; i++) {
      curr += arr[i];
      mod[i] = curr % N;
      if(hash.containsKey(mod[i])) {
        int j = hash.get(mod[i]);
        int result[] = new int[i-j];
        System.arraycopy(arr, j+1, result, 0, i-j);
        return result;
      } else {
        hash.put(mod[i], i);
      }
    }
    return null;
  }

If my logic above is correct, then the runtime is O(n).

Working code

#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
#include<iterator>
typedef std::list<std::vector<int>> subarraylist;

subarraylist getSubArrays(std::vector<int> num) {
	subarraylist salist;
	int len = num.size();

	int saStart = 0;
	int saEnd = 1;
	int sum = num[saStart];

	std::vector<int>::const_iterator start = num.begin();

	while(saStart <= len-1) {
		while(saEnd <= len-1 && sum < len) {
			sum += num[saEnd];
			saEnd++;
		}
		if(sum == len) {
			std::vector<int> sa(start + saStart, start + saEnd);
			salist.push_back(sa);
		}
		saStart++;
		saEnd = saStart + 1;
		sum = num[saStart];	
	}

	return salist;
}

void printSubArray(std::vector<int> num) {
	std::copy(num.begin(), num.end(), std::ostream_iterator<int>(std::cout, " "));	
}

int main() {

	std::vector<int> num;
	std::cout << "Enter numbers\n";
	int temp = 0;
	while (std::cin >> temp) {
		num.push_back(temp);
	}
	subarraylist subarrays;
	
	subarrays = getSubArrays(num);
	std::cout << "Subarrays are \n";
	
	for(subarraylist::iterator i = subarrays.begin(); i != subarrays.end(); ++i) {
		printSubArray(static_cast<std::vector<int> >(*i));
		std::cout << "\n";
	}

	return 0;
}