TapeEquilibrium at app.codility.com-programmers in C plus Plus Explained
Foreword: Category of Article - Technology, Computers and Software, Algorithm
By: Chrysanthus Date Published: 21 Jan 2024
Task
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(Nxlog(N))
Lesson 3 at app.codility.com/programmers
The solution and its explanation are given below.
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] = 3
We 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(vector<int> &A);
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] = 3
the 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].
Notes:
P is an index variable of the array (vector) from 1 to N-1.
In the problem, it is mentioned towards the bottom, that the maximum possible value in the array (vector) is 1000. Assuming that the first element of the array is 0 and the rest of the elements of the array are 1000, then the absolute maximum difference is (N-1) x 1000, where N is the number of array elements given. If this is made N x 1000, the resulting program will still be alright.
So, in the solution, the initial absolute minimum difference would be considered as N x 1000. When the actual first absolute minimum difference is obtained, it is compared to N x 1000. It will likely be smaller and that will be the new minimum. The next absolute difference obtained will be compared to this new minimum; and if it is smaller, it will become the next new minimum. This will continue till the end of the array.
This task can be solved in a brute force way or in a smarter way. The smarter way given below, obtains 100% for correctness and performance, and 100% total score, at app.codility.com/programmers. However, the brute-force method is treated first.
Brute-Force Solution
In the brute force solution, there are three for-loops: one outer for-loop and two nested for-loops at the same level. For each iteration of the outer for-loop, the first nested for-loop does the sum for the left-hand part of the array; and the second nested for-loop, does the right-hand sum of the array. The subtraction and comparison takes place in the outer for-loop below. The brute force code is (read the code and comments):
#include <iostream>
#include <vector>
using namespace std;
int solution(vector<int> &A) {
int N = A.size();
int adsMinDiff = 1000 * N;
for (int p = 1; p < N; p++) {
int leftSum = 0; //sum of left part
int rightSum = 0; //sum of right part
for (int i=0; i<p; i++)
leftSum = leftSum + A[i];
for (int j=p; j<N; j++)
rightSum = rightSum + A[j];
int diff = rightSum - leftSum;
if (diff < 0)
diff = -diff; //to obtain absolute difference
if (diff < adsMinDiff)
adsMinDiff = diff;
}
return adsMinDiff;
}
The result from app.codility.com with this brute force, is
Task score : 69% - Correctness : 100% ; Performance : 33%
Detected time complexity: O(N * N) = O(n2)
This means that the correct answer for the absolute minimum difference is always obtained for any given array, with this method, but the speed is slow, especially for long arrays.
Smarter Solution
Having gotten the totalSum, only one scan through all the elements in the array is necessary again. For each element, A[P] as the scanning continues, the current leftSum is obtained by just adding the new left element to the previous leftSum, and the rightSum is obtained by just subtracting the leftSum from the totalSum. The current difference is then determined. The immediate result (current difference) may be positive or negative. If it is negative, it has to be made positive, by just multiplying with -1. Remember, it is the absolute difference that is required. This is the new temporary minimum, which has to be compared with the next minimum. The code is (read through the code and comments):
#include <iostream>
#include <vector>
using namespace std;
int solution(vector<int> &A) {
int N = A.size();
int totalSum = 0;
for (int i = 0; i < N; ++i) {
totalSum += A[i];
}
int adsMinDiff = 1000 * N;
int leftSum = 0;
for (int i = 1; i < N; i++) {
leftSum = leftSum + A[i-1];
int rightSum = totalSum - leftSum;
int diff = leftSum - rightSum;
if (diff < 0)
diff = -diff; //to obtain absolute difference, equivalent to x -1.
if (diff < adsMinDiff)
adsMinDiff = diff;
}
return adsMinDiff;
}
int main()
{
vector<int> B{3, 1, 2, 4, 3};
int minl = solution(B);
cout << minl << endl;
return 0;
}
Remember that the C++ main() function cannot be submitted at app.codility.com/programmers . The reader should also register, free at app.codility.com, in order to be testing his/her code (solutions). The reader should also read the above two code solutions, to really understand what is going on, especially in the parentheses of the for-loops. From app.codility.com :
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N)
The speed is now high. The detected time complexity is O(N). This needs explanation:
There are two separate for-loops in the smarter code. Determining the totalSum with the first for-loop took one pass (one scan). The second for-loop also does one pass, but in each iteration, there are a good number of statements. In the first for-loop, there is only one statement. So the second for-loop takes much longer to complete, than the first for-loop. So, app.codility.com/programmers ignores the first for-loop, and says that the time complexity is O(n).
Conclusion
To solve the problem or a similar one, get the total-sum first, in one scan. In another scan, get the left and right totals for each element, and before the next iterator, get the difference, its absolute value, and do a comparison. The final answer is the least value compared.