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:

func Solution(A []int) int

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 Go

Time spent on task 1 minutes

Notes

not defined yet

Code: 10:35:34 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: 10:35:45 UTC, go, 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 29 30 31 32 33 34 35 36 37 38

package solution

// you can also use imports, for example:
// import "fmt"
// import "os"

// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")

func solution(stacks []int) int {
    size := len(stacks)
    moveRight := make([]int, size, size)
    moveLeft := make([]int, size, size)
    copy(moveRight, stacks)
    copy(moveLeft, stacks)

    for i := 1; i < size; i++ {
        reverseIndex := size - 1 - i
        moveRight[i] += (moveRight[i-1]) / 2
        moveLeft[reverseIndex] += (moveLeft[reverseIndex+1]) / 2
    }

    highestStack := 0
    for i := 0; i < size; i++ {
        stack := stacks[i]
        if i > 0 {
            stack += moveRight[i-1] / 2
        }
        if i < size-1 {
            stack += moveLeft[i+1] / 2
        }
        if stack > highestStack {
            highestStack = stack
        }
    }

    return highestStack
}

Code: 10:35:52 UTC, go, 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 29 30 31 32 33 34 35 36 37 38

package solution

// you can also use imports, for example:
// import "fmt"
// import "os"

// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")

func solution(stacks []int) int {
    size := len(stacks)
    moveRight := make([]int, size, size)
    moveLeft := make([]int, size, size)
    copy(moveRight, stacks)
    copy(moveLeft, stacks)

    for i := 1; i < size; i++ {
        reverseIndex := size - 1 - i
        moveRight[i] += (moveRight[i-1]) / 2
        moveLeft[reverseIndex] += (moveLeft[reverseIndex+1]) / 2
    }

    highestStack := 0
    for i := 0; i < size; i++ {
        stack := stacks[i]
        if i > 0 {
            stack += moveRight[i-1] / 2
        }
        if i < size-1 {
            stack += moveLeft[i+1] / 2
        }
        if stack > highestStack {
            highestStack = stack
        }
    }

    return highestStack
}

Analysis

Compile error

# main
workspace/src/main/exec.go:6: imported and not used: "solution"
workspace/src/main/exec.go:157: undefined: Solution

Code: 10:36:01 UTC, go, 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 27 28 29 30 31 32 33 34 35 36 37 38

package solution

// you can also use imports, for example:
// import "fmt"
// import "os"

// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")

func Solution(stacks []int) int {
    size := len(stacks)
    moveRight := make([]int, size, size)
    moveLeft := make([]int, size, size)
    copy(moveRight, stacks)
    copy(moveLeft, stacks)

    for i := 1; i < size; i++ {
        reverseIndex := size - 1 - i
        moveRight[i] += (moveRight[i-1]) / 2
        moveLeft[reverseIndex] += (moveLeft[reverseIndex+1]) / 2
    }

    highestStack := 0
    for i := 0; i < size; i++ {
        stack := stacks[i]
        if i > 0 {
            stack += moveRight[i-1] / 2
        }
        if i < size-1 {
            stack += moveLeft[i+1] / 2
        }
        if stack > highestStack {
            highestStack = stack
        }
    }

    return highestStack
}

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: 10:36:06 UTC, go, 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 27 28 29 30 31 32 33 34 35 36 37 38

package solution

// you can also use imports, for example:
// import "fmt"
// import "os"

// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")

func Solution(stacks []int) int {
    size := len(stacks)
    moveRight := make([]int, size, size)
    moveLeft := make([]int, size, size)
    copy(moveRight, stacks)
    copy(moveLeft, stacks)

    for i := 1; i < size; i++ {
        reverseIndex := size - 1 - i
        moveRight[i] += (moveRight[i-1]) / 2
        moveLeft[reverseIndex] += (moveLeft[reverseIndex+1]) / 2
    }

    highestStack := 0
    for i := 0; i < size; i++ {
        stack := stacks[i]
        if i > 0 {
            stack += moveRight[i-1] / 2
        }
        if i < size-1 {
            stack += moveLeft[i+1] / 2
        }
        if stack > highestStack {
            highestStack = stack
        }
    }

    return highestStack
}

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: 10:36:09 UTC, go, 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 27 28 29 30 31 32 33 34 35 36 37 38

package solution

// you can also use imports, for example:
// import "fmt"
// import "os"

// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")

func Solution(stacks []int) int {
    size := len(stacks)
    moveRight := make([]int, size, size)
    moveLeft := make([]int, size, size)
    copy(moveRight, stacks)
    copy(moveLeft, stacks)

    for i := 1; i < size; i++ {
        reverseIndex := size - 1 - i
        moveRight[i] += (moveRight[i-1]) / 2
        moveLeft[reverseIndex] += (moveLeft[reverseIndex+1]) / 2
    }

    highestStack := 0
    for i := 0; i < size; i++ {
        stack := stacks[i]
        if i > 0 {
            stack += moveRight[i-1] / 2
        }
        if i < size-1 {
            stack += moveLeft[i+1] / 2
        }
        if stack > highestStack {
            highestStack = stack
        }
    }

    return highestStack
}

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.016 s

0.028 s

0.016 s

▶

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

✔

0.028 s

0.020 s

▶

random_large
Heights of stacks are randomly generated.

✔

0.028 s