Popular Posts

Monday, May 28, 2012

Sub array which forms the given sum

Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.

 private static void checkSumExists(int[] a, int pRequiredSum) {
int length = a.length;
int currentSum = a[0];
int startIndex = 0;

for (int i = 1; i < length; i++) {
while (currentSum > pRequiredSum && startIndex<i-1) {
currentSum = currentSum - a[startIndex];
startIndex++;
}

if (currentSum == pRequiredSum) {
System.out.println("SubArray with startIndex : " + startIndex
+ " and endIndex : " + (i - 1)
+ " makes the given sum :" + pRequiredSum);
return ;
}

currentSum = currentSum + a[i];
}

System.out
.println("Sub array which makes the required sum doesn't exist : "
+ pRequiredSum);
}
Refer : http://www.geeksforgeeks.org/archives/19267

No comments:

Post a Comment