happycoding/Equi.cpp at master · hellocomrade/happycoding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//http://blog.codility.com/2011/03/solutions-for-task-equi.html
#include <vector>
#include <cassert>
#include <iostream>

using namespace std;

//very tricky boundary condition:
//Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N.1.
//But I think my solution is better than the one on their blog...
int solutionEqui(const vector<int> &A) {
    int len = A.size();
    if (len == 0)
	return -1;
    if (len == 1)
	return 0;
    vector<long long> prefixsum(len+1, 0);
    for (int i = 1; i<=len; ++i)
	prefixsum[i] = prefixsum[i - 1] + A[i-1];
    long long sum = prefixsum[len];
    for (int i = 1; i<len+1; ++i)
	if (prefixsum[i-1] == sum - prefixsum[i])
	    return i-1;
    return -1;
}
//https://codility.com/demo/results/demoZ59B7J-6BS/
int solutionEqui1(const vector<int> &A) {
    int len = A.size(), ans = -1;
    if(len > 0) {
        vector<long long> memo(len + 1, 0LL);
        memo[0] = 0LL;
        for(int i = 1; i <= len; ++i)
            memo[i] = memo[i - 1] + A[i - 1];
        for(int i = 1; i <= len; ++i) {
            if(memo[i - 1] == memo[len] - memo[i]) {
                ans = i - 1;
                break;
            }
        }
    }
    return ans;
}
void testEqui()
{
    cout << "Expect 1: " << solutionEqui(vector<int>({ -1, 3, -4, 5, 1, -6, 2, 1 })) << endl;
    cout << "Expect 2: " << solutionEqui(vector<int>({ 1,2,6,0,1,1,1 })) << endl;
    cout << "Expect 0: " << solutionEqui(vector<int>({ 1, 2, 6, -9,1})) << endl;
    cout << "Expect 0: " << solutionEqui(vector<int>({ 100 })) << endl;
    cout << "Expect 0: " << solutionEqui(vector<int>({ 500, 1, -2, -1, 2 })) << endl;
    cout << "Expect 0: " << solutionEqui(vector<int>({ -1,0 })) << endl;
    cout << "Expect 0: " << solutionEqui(vector<int>({ -1, -1, 1 })) << endl;
    cout << "Expect 0: " << solutionEqui(vector<int>({ -1, 0, 0 })) << endl;
    cout << "Expect 0: " << solutionEqui(vector<int>({ 1, 1, -1 })) << endl;
}