Test results - Codility

Tasks Details

medium

1. StacksOfCoins

Move coins between the given stacks to obtain a stack with the maximum possible number of coins.

Task Score

100%

Correctness

100%

Performance

100%

There are N stacks of coins, numbered from 0 to N−1. The Kth stack has A[K] coins. In one move we can pick two coins from any stack we choose, put the first coin away and place the second coin on the adjacent stack (either to the left or to the right of the original stack).

What is the maximum number of coins that can be accumulated in a single stack?

Write a function:

int solution(vector<int> &A);

that, given an array A of N integers, recording the heights of the stacks, returns the maximum number of coins that can be accumulated in one stack after performing any number of moves as described above.

Examples:

1. Given A = [2, 3, 1, 3], the function should return 5. A possible sequence of moves is: [2, 3, 1, 3] → [0, 4, 1, 3] → [0, 4, 2, 1] → [0, 5, 0, 1].

2. Given A = [3, 7, 0, 5], the function should return 9. A possible sequence of moves is: [3, 7, 0, 5] → [1, 8, 0, 5] → [1, 8, 1, 3] → [1, 8, 2, 1] → [1, 9, 0, 1].

3. Given A = [1, 1, 1, 1, 1], the function should return 1. No move can be performed.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..200,000];

each element of array A is an integer within the range [0..100,000,000].

Solution

Programming language used C++

Time spent on task 2 minutes

Notes

not defined yet

Code: 19:33:13 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
    }
}

Code: 19:33:23 UTC, java, autosave

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    if(A.empty()) return 0;
    if(A.size() == 1) return A.front();
    vector<int> left(A.size(), 0), right(A.size(), 0);
    left[0] = A[0];
    for(int i = 1; i != A.size(); ++i){
        left[i] = left[i-1]/2 + A[i];
    }
    right.back() = A.back();
    for(int i = A.size()-2; i >= 0; --i){
        right[i] = right[i+1]/2 + A[i];
    }
    int result = max(A[0] + right[1]/2, A.back() + left[A.size()-1]/2);
    for(int i = 1; i != A.size()-1; ++i){
        int current = A[i] + left[i-1]/2 + right[i+1]/2;
        if(result < current) result = current;
    }
    return result;
}
}

Code: 19:34:10 UTC, java, autosave

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    if(A.empty()) return 0;
    if(A.size() == 1) return A.front();
    vector<int> left(A.size(), 0), right(A.size(), 0);
    left[0] = A[0];
    for(int i = 1; i != A.size(); ++i){
        left[i] = left[i-1]/2 + A[i];
    }
    right.back() = A.back();
    for(int i = A.size()-2; i >= 0; --i){
        right[i] = right[i+1]/2 + A[i];
    }
    int result = max(A[0] + right[1]/2, A.back() + left[A.size()-2]/2);
    for(int i = 1; i != A.size()-1; ++i){
        int current = A[i] + left[i-1]/2 + right[i+1]/2;
        if(result < current) result = current;
    }
    return result;
}
}

Code: 19:34:15 UTC, java, verify, result: Failed

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    if(A.empty()) return 0;
    if(A.size() == 1) return A.front();
    vector<int> left(A.size(), 0), right(A.size(), 0);
    left[0] = A[0];
    for(int i = 1; i != A.size(); ++i){
        left[i] = left[i-1]/2 + A[i];
    }
    right.back() = A.back();
    for(int i = A.size()-2; i >= 0; --i){
        right[i] = right[i+1]/2 + A[i];
    }
    int result = max(A[0] + right[1]/2, A.back() + left[A.size()-2]/2);
    for(int i = 1; i != A.size()-1; ++i){
        int current = A[i] + left[i-1]/2 + right[i+1]/2;
        if(result < current) result = current;
    }
    return result;
}
}

Analysis

Compile error

Solution.java:8: error: <identifier> expected
int solution(vector<int> &A) {
                        ^
Solution.java:8: error: ';' expected
int solution(vector<int> &A) {
                          ^
Solution.java:8: error: illegal start of type
int solution(vector<int> &A) {
                           ^
Solution.java:8: error: <identifier> expected
int solution(vector<int> &A) {
                            ^
Solution.java:8: error: ';' expected
int solution(vector<int> &A) {
                              ^
Solution.java:10: error: illegal start of type
    if(A.empty()) return 0;
      ^
Solution.java:10: error: ';' expected
    if(A.empty()) return 0;
        ^
Solution.java:10: error: invalid method declaration; return type required
    if(A.empty()) return 0;
         ^
Solution.java:10: error: ';' expected
    if(A.empty()) return 0;
                ^
Solution.java:11: error: illegal start of type
    if(A.size() == 1) return A.front();
    ^
Solution.java:11: error: <identifier> expected
    if(A.size() == 1) return A.front();
             ^
Solution.java:11: error: ';' expected
    if(A.size() == 1) return A.front();
              ^
Solution.java:11: error: illegal start of type
    if(A.size() == 1) return A.front();
                ^
Solution.java:11: error: <identifier> expected
    if(A.size() == 1) return A.front();
                  ^
Solution.java:11: error: ';' expected
    if(A.size() == 1) return A.front();
                    ^
Solution.java:11: error: illegal start of type
    if(A.size() == 1) return A.front();
                      ^
Solution.java:11: error: ';' expected
    if(A.size() == 1) return A.front();
                              ^
Solution.java:11: error: invalid method declaration; return type required
    if(A.size() == 1) return A.front();
                               ^
Solution.java:12: error: <identifier> expected
    vector<int> left(A.size(), 0), right(A.size(), 0);
                           ^
Solution.java:12: error: ';' expected
    vector<int> left(A.size(), 0), right(A

Code: 19:34:39 UTC, cpp, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
}

Code: 19:34:52 UTC, cpp, autosave

show code in pop-up

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

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    if(A.empty()) return 0;
    if(A.size() == 1) return A.front();
    vector<int> left(A.size(), 0), right(A.size(), 0);
    left[0] = A[0];
    for(int i = 1; i != A.size(); ++i){
        left[i] = left[i-1]/2 + A[i];
    }
    right.back() = A.back();
    for(int i = A.size()-2; i >= 0; --i){
        right[i] = right[i+1]/2 + A[i];
    }
    int result = max(A[0] + right[1]/2, A.back() + left[A.size()-1]/2);
    for(int i = 1; i != A.size()-1; ++i){
        int current = A[i] + left[i-1]/2 + right[i+1]/2;
        if(result < current) result = current;
    }
    return result;
}

Code: 19:34:59 UTC, cpp, verify, result: Passed

show code in pop-up

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

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    if(A.empty()) return 0;
    if(A.size() == 1) return A.front();
    vector<int> left(A.size(), 0), right(A.size(), 0);
    left[0] = A[0];
    for(int i = 1; i != A.size(); ++i){
        left[i] = left[i-1]/2 + A[i];
    }
    right.back() = A.back();
    for(int i = A.size()-2; i >= 0; --i){
        right[i] = right[i+1]/2 + A[i];
    }
    int result = max(A[0] + right[1]/2, A.back() + left[A.size()-2]/2);
    for(int i = 1; i != A.size()-1; ++i){
        int current = A[i] + left[i-1]/2 + right[i+1]/2;
        if(result < current) result = current;
    }
    return result;
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.001 s

▶

example2
Second example test.

✔

0.001 s

▶

example3
Third example test.

✔

0.001 s

Code: 19:35:06 UTC, cpp, verify, result: Passed

show code in pop-up

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

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    if(A.empty()) return 0;
    if(A.size() == 1) return A.front();
    vector<int> left(A.size(), 0), right(A.size(), 0);
    left[0] = A[0];
    for(int i = 1; i != A.size(); ++i){
        left[i] = left[i-1]/2 + A[i];
    }
    right.back() = A.back();
    for(int i = A.size()-2; i >= 0; --i){
        right[i] = right[i+1]/2 + A[i];
    }
    int result = max(A[0] + right[1]/2, A.back() + left[A.size()-2]/2);
    for(int i = 1; i != A.size()-1; ++i){
        int current = A[i] + left[i-1]/2 + right[i+1]/2;
        if(result < current) result = current;
    }
    return result;
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.001 s

▶

example2
Second example test.

✔

0.001 s

▶

example3
Third example test.

✔

0.001 s

Code: 19:35:09 UTC, cpp, final, score: 100

show code in pop-up

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

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    if(A.empty()) return 0;
    if(A.size() == 1) return A.front();
    vector<int> left(A.size(), 0), right(A.size(), 0);
    left[0] = A[0];
    for(int i = 1; i != A.size(); ++i){
        left[i] = left[i-1]/2 + A[i];
    }
    right.back() = A.back();
    for(int i = A.size()-2; i >= 0; --i){
        right[i] = right[i+1]/2 + A[i];
    }
    int result = max(A[0] + right[1]/2, A.back() + left[A.size()-2]/2);
    for(int i = 1; i != A.size()-1; ++i){
        int current = A[i] + left[i-1]/2 + right[i+1]/2;
        if(result < current) result = current;
    }
    return result;
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

expand all Example tests

▶

example1
First example test.

✔

0.001 s

▶

example2
Second example test.

✔

0.001 s

▶

example3
Third example test.

✔

0.001 s

expand all Correctness tests

▶

small
N <= 5.

✔

0.001 s

▶

equal_small
All numbers are the same. N = 100.

✔

0.001 s

▶

random_small
Heights of stacks are randomly generated. N = 100.

✔

0.001 s

▶

sorted_medium
Stacks are sorted by height (decreasingly or increasingly). N = 1,000.

✔

0.001 s

▶

random_medium
Heights of stacks are randomly generated. N = 1,000.

✔

0.001 s

expand all Performance tests

▶

almost_equal_large
Stacks have similar heights (differ by at most 10).

✔

0.008 s

0.024 s

0.012 s

▶

sorted_large
Stacks are sorted by height (decreasingly or increasingly).

✔

0.020 s

0.016 s

▶

random_large
Heights of stacks are randomly generated.

✔

0.020 s