Equal Stacks

See the original problem on HackerRank.

Solutions

C++ Solution very pretty much independent from the number of the stacks (just change numberOfStacks):

 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
const int numberOfStacks = 3;

array<int, numberOfStacks> n{};
for (auto& i : n)
    cin >> i;

array<vector<int>, numberOfStacks> stacks;
array<int, numberOfStacks> heights{};

for (auto i=0; i<n.size(); ++i)
{
    auto& s = stacks[i];
    s.resize(n[i]);
    copy_n(istream_iterator<int>(cin), n[i], begin(s));
    reverse(begin(s), end(s));
    // we may even accumulate while we read 
    heights[i] = accumulate(begin(s), end(s), 0);
}

while (!equal(next(begin(heights)), end(heights), begin(heights)))
{
    auto maxIt = max_element(begin(heights), end(heights));
    auto maxIdx = distance(begin(heights), maxIt);
    heights[maxIdx] -= stacks[maxIdx].back();
    stacks[maxIdx].pop_back();
}

cout << heights.front();

Basically, we first calculate the heights of all the stacks (sum of the elements of each) and then we remove one element from the tallest until all the heights are the same.

Prefix sum solutions

An alternative solution is based on the concept of prefix sum. Basically, we can calculate the prefix sum of all the stacks and find the maximum intersection:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
n1, n2, n3 = map(int, raw_input().split())
s1 = [0] + map(int, raw_input().split())[::-1]
s2 = [0] + map(int, raw_input().split())[::-1]
s3 = [0] + map(int, raw_input().split())[::-1]

for i in xrange(1, len(s1)):
    s1[i] += s1[i-1]
for i in xrange(1, len(s2)):
    s2[i] += s2[i-1]
for i in xrange(1, len(s3)):
    s3[i] += s3[i-1]
print max(set(s1) & set(s2) & set(s3))
We've worked on this challenge in these gyms: modena  padua  milan  barcelona  turin  rome 
comments powered by Disqus