A non-empty array A consisting of N integers is given. Array A represents numbers on a tape.
Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].
The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|
In other words, it is the absolute difference between the sum of the first part and the sum of the second part.
For example, consider array A such that:
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3We can split this tape in four places:
- P = 1, difference = |3 − 10| = 7
- P = 2, difference = |4 − 9| = 5
- P = 3, difference = |6 − 7| = 1
- P = 4, difference = |10 − 3| = 7
Write a function:
int solution(int A[], int N);
that, given a non-empty array A of N integers, returns the minimal difference that can be achieved.
For example, given:
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3the function should return 1, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [2..100,000];
- each element of array A is an integer within the range [−1,000..1,000].
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
long p;
long index;
long leftSum;
long rightSum;
long totalSum=0;
long last_minimum=100000;
long current_min;
if(N==2) return abs(A[0]-A[1]);
if(N==1) return abs(A[0]);
for(index=0; index < N; index++)
totalSum = totalSum + A[index];
//if (totalSum == 0)
// return totalSum;
//last_minimum = totalSum;
printf("\nTotal Sum: %ld\n", totalSum);
leftSum = 0; rightSum = 0;
for (p = 1; p <= N-1; p++) {
leftSum += A[p - 1];
rightSum = totalSum - leftSum;
current_min = abs((long)(leftSum - rightSum));
last_minimum = current_min < last_minimum ? current_min : last_minimum;
if (last_minimum == 0)
break;
printf("\nP = %ld, difference=|%lld - %lld| = %lld\n", p, leftSum, rightSum, current_min);
}
printf("\nMinimum is %ld\n", last_minimum);
return last_minimum;
}
int abs(int n) {
return (n >= 0) ? n : (-(n));
}
WARNING: producing output may seriously slow down your code! Total Sum: 13 P = 1, difference=|42949672963 - -4641296313239994361| = 645791591998721168 P = 2, difference=|38654705668 - -4641296313239994363| = 645791591998721168 P = 3, difference=|30064771078 - -4641296313239994367| = 645791591998721168 P = 4, difference=|12884901898 - -4641296313239994361| = 645791591998721168 Minimum is 1
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
long p;
long index;
long leftSum;
long rightSum;
long totalSum=0;
long last_minimum=100000;
long current_min;
if(N==2) return abs(A[0]-A[1]);
if(N==1) return abs(A[0]);
for(index=0; index < N; index++)
totalSum = totalSum + A[index];
//if (totalSum == 0)
// return totalSum;
//last_minimum = totalSum;
printf("\nTotal Sum: %ld\n", totalSum);
leftSum = 0; rightSum = 0;
for (p = 1; p <= N-1; p++) {
leftSum += A[p - 1];
rightSum = totalSum - leftSum;
current_min = abs((long)(leftSum - rightSum));
last_minimum = current_min < last_minimum ? current_min : last_minimum;
if (last_minimum == 0)
break;
printf("\nP = %ld, difference=|%ld - %ld| = %ld\n", p, leftSum, rightSum, current_min);
}
printf("\nMinimum is %ld\n", last_minimum);
return last_minimum;
}
int abs(int n) {
return (n >= 0) ? n : (-(n));
}
WARNING: producing output may seriously slow down your code! Total Sum: 13 P = 1, difference=|3 - 10| = 7 P = 2, difference=|4 - 9| = 5 P = 3, difference=|6 - 7| = 1 P = 4, difference=|10 - 3| = 7 Minimum is 1
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
long p;
long index;
long leftSum;
long rightSum;
long totalSum=0;
long last_minimum=100000;
long current_min;
if(N==2) return abs(A[0]-A[1]);
if(N==1) return abs(A[0]);
for(index=0; index < N; index++)
totalSum = totalSum + A[index];
//if (totalSum == 0)
// return totalSum;
//last_minimum = totalSum;
//printf("\nTotal Sum: %ld\n", totalSum);
leftSum = 0; rightSum = 0;
for (p = 1; p <= N-1; p++) {
leftSum += A[p - 1];
rightSum = totalSum - leftSum;
current_min = abs((long)(leftSum - rightSum));
last_minimum = current_min < last_minimum ? current_min : last_minimum;
if (last_minimum == 0)
break;
//printf("\nP = %ld, difference=|%ld - %ld| = %ld\n", p, leftSum, rightSum, current_min);
}
//printf("\nMinimum is %ld\n", last_minimum);
return last_minimum;
}
int abs(int n) {
return (n >= 0) ? n : (-(n));
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
long p;
long index;
long leftSum;
long rightSum;
long totalSum=0;
long last_minimum=100000;
long current_min;
if(N==2) return abs(A[0]-A[1]);
if(N==1) return abs(A[0]);
for(index=0; index < N; index++)
totalSum = totalSum + A[index];
leftSum = 0; rightSum = 0;
for (p = 1; p <= N-1; p++) {
leftSum += A[p - 1];
rightSum = totalSum - leftSum;
current_min = abs((long)(leftSum - rightSum));
last_minimum = current_min < last_minimum ? current_min : last_minimum;
if (last_minimum == 0)
break;
}
return last_minimum;
}
int abs(int n) {
return (n >= 0) ? n : (-(n));
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
long p;
long index;
long leftSum;
long rightSum;
long totalSum=0;
long last_minimum=100000;
long current_min;
if(N==2) return abs(A[0]-A[1]);
if(N==1) return abs(A[0]);
for(index=0; index < N; index++)
totalSum = totalSum + A[index];
leftSum = 0; rightSum = 0;
for (p = 1; p <= N-1; p++) {
leftSum += A[p - 1];
rightSum = totalSum - leftSum;
current_min = abs((long)(leftSum - rightSum));
last_minimum = current_min < last_minimum ? current_min : last_minimum;
if (last_minimum == 0)
break;
}
return last_minimum;
}
int abs(int n) {
return (n >= 0) ? n : (-(n));
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
long p;
long index;
long leftSum;
long rightSum;
long totalSum=0;
long last_minimum=100000;
long current_min;
if(N==2) return abs(A[0]-A[1]);
if(N==1) return abs(A[0]);
for(index=0; index < N; index++)
totalSum = totalSum + A[index];
leftSum = 0; rightSum = 0;
for (p = 1; p <= N-1; p++) {
leftSum += A[p - 1];
rightSum = totalSum - leftSum;
current_min = abs((long)(leftSum - rightSum));
last_minimum = current_min < last_minimum ? current_min : last_minimum;
if (last_minimum == 0)
break;
}
return last_minimum;
}
int abs(int n) {
return (n >= 0) ? n : (-(n));
}
The solution obtained perfect score.