Just finish a fun question from Hackerrank: Sherlock and Array
Question description:
Watson gives Sherlock an array AA of length NN. Then he asks him to determine if there exists an element in the array such that the sum of the elements on its left is equal to the sum of the elements on its right. If there are no elements to the left/right, then the sum is considered to be zero.
Formally, find an ii, such that, AA1+A+A2…A…Ai-1 =A=Ai+1+A+Ai+2…A…AN.
My approach is to go through array and on each iteration adjust sum on the left and sum on the right by current integer from array. Complexity of this approach is O(n). Code below:
#import <Foundation/Foundation.h>
int main (int argc, const char * argv[]) {
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
int numberOfTestCases;
scanf("%d", &numberOfTestCases);
for (int i=0; i<numberOfTestCases; i++) {
NSMutableArray *inputIntegers = [NSMutableArray new];
BOOL sumExists = NO;
int numberOfElements;
int sumLeft = 0;
int sumRight = 0;
scanf("%d", &numberOfElements);
for (int j=0; j<numberOfElements; j++) {
int inputElement;
scanf("%d", &inputElement);
[inputIntegers addObject:[NSNumber numberWithInt:inputElement]];
sumRight+=[inputIntegers[j] integerValue];
}
for (int j=0; j<numberOfElements; j++) {
sumRight -= [inputIntegers[j] integerValue];
if (sumLeft == sumRight){
sumExists = YES;
break;
} else {
sumLeft += [inputIntegers[j] integerValue];
}
}
printf("%s\n", sumExists ? "YES" : "NO");
}
);
[pool drain];
return 0;
}