Test results - Codility

Tasks Details

medium

1. CountNonDivisible

Calculate the number of elements of an array that are not divisors of each element.

Task Score

100%

Correctness

100%

Performance

100%

You are given an array A consisting of N integers.

For each number A[i] such that 0 ≤ i < N, we want to count the number of elements of the array that are not the divisors of A[i]. We say that these elements are non-divisors.

For example, consider integer N = 5 and array A such that:

A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 3 A[4] = 6

For the following elements:

A[0] = 3, the non-divisors are: 2, 6,

A[1] = 1, the non-divisors are: 3, 2, 3, 6,

A[2] = 2, the non-divisors are: 3, 3, 6,

A[3] = 3, the non-divisors are: 2, 6,

A[4] = 6, there aren't any non-divisors.

Write a function:

func Solution(A []int) []int

that, given an array A consisting of N integers, returns a sequence of integers representing the amount of non-divisors.

Result array should be returned as an array of integers.

For example, given:

A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 3 A[4] = 6

the function should return [2, 4, 3, 2, 0], as explained above.

Write an efficient algorithm for the following assumptions:

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

each element of array A is an integer within the range [1..2 * N].

Solution

Programming language used Go

Time spent on task 7 minutes

Notes

not defined yet

Code: 19:10:22 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:10:25 UTC, go, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

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(A []int) []int {
    // write your code in Go 1.4
}

Code: 19:10:40 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 39 40 41 42 43 44 45 46 47 48 49 50

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 SqrtInt(n int) int {
	return int(math.Sqrt(float64(n)))
}

// PREVIOUS RESULT: https://app.codility.com/demo/results/trainingNW9MNY-B5Q/
func Solution(A []int) []int {
	n := len(A)
	max, counts := 0, make([]int, n*2+1, n*2+1) // A[i] is <= 2*N

	// calc counts and max
	for i := 0; i < n; i++ {
		counts[A[i]]++

		if max < A[i] {
			max = A[i]
		}
	}

	// Sieve of 'max' also helps us to count the number of
	// all the divisors of all the numbers upto and including 'max'
	divs := make([]int, max+1, max+1)
	for i := 2; i*i <= max; i++ {
		for j := i * i; j <= max; j += i {
			// sum of counts of divisors (excludes 1's and number itself)
			divs[j] += counts[i]
			if j/i != i {
				divs[j] += counts[j/i]
			}
		}
	}

	// calc the non-divisors
	res := make([]int, n, n)
	for i := 0; i < n; i++ {
		a := A[i]
		// also discount the counts of 1s and number itself
		res[i] = n - (divs[a] + counts[a] + counts[1])
	}

	return res
}

Code: 19:10:49 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 39 40 41 42 43 44 45 46 47 48 49 50

package solution

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

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

func SqrtInt(n int) int {
	return int(math.Sqrt(float64(n)))
}

// PREVIOUS RESULT: https://app.codility.com/demo/results/trainingNW9MNY-B5Q/
func Solution(A []int) []int {
	n := len(A)
	max, counts := 0, make([]int, n*2+1, n*2+1) // A[i] is <= 2*N

	// calc counts and max
	for i := 0; i < n; i++ {
		counts[A[i]]++

		if max < A[i] {
			max = A[i]
		}
	}

	// Sieve of 'max' also helps us to count the number of
	// all the divisors of all the numbers upto and including 'max'
	divs := make([]int, max+1, max+1)
	for i := 2; i*i <= max; i++ {
		for j := i * i; j <= max; j += i {
			// sum of counts of divisors (excludes 1's and number itself)
			divs[j] += counts[i]
			if j/i != i {
				divs[j] += counts[j/i]
			}
		}
	}

	// calc the non-divisors
	res := make([]int, n, n)
	for i := 0; i < n; i++ {
		a := A[i]
		// also discount the counts of 1s and number itself
		res[i] = n - (divs[a] + counts[a] + counts[1])
	}

	return res
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got [2, 3, 3, 2, 0] expected [2, 4, 3, 2, 0]

0.001 s

WRONG ANSWER, got [2, 3, 3, 2, 0] expected [2, 4, 3, 2, 0]

Code: 19:16:52 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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

package solution

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

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

func SqrtInt(n int) int {
	return int(math.Sqrt(float64(n)))
}

// PREVIOUS RESULT: https://app.codility.com/demo/results/trainingNW9MNY-B5Q/
func Solution(A []int) []int {
	n := len(A)
	max, counts := 0, make([]int, n*2+1, n*2+1) // A[i] is <= 2*N

	// calc counts and max
	for i := 0; i < n; i++ {
		counts[A[i]]++

		if max < A[i] {
			max = A[i]
		}
	}

	// Sieve of 'max' also helps us to count the number of
	// all the divisors of all the numbers upto and including 'max'
	divs := make([]int, max+1, max+1)
	for i := 2; i*i <= max; i++ {
		for j := i * i; j <= max; j += i {
			// sum of counts of divisors (excludes 1's and number itself)
			divs[j] += counts[i]
			if j/i != i {
				divs[j] += counts[j/i]
			}
		}
	}

	// calc the non-divisors
	res := make([]int, n, n)
	for i := 0; i < n; i++ {
		a := A[i]
		// discount the counts of number itself
		res[i] = n - (divs[a] + counts[a])
		// also discount the counts of 1's
		if a != 1 {
			res[i] -= counts[1]
		}
	}

	return res
}

Code: 19:16:55 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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

package solution

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

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

func SqrtInt(n int) int {
	return int(math.Sqrt(float64(n)))
}

// PREVIOUS RESULT: https://app.codility.com/demo/results/trainingNW9MNY-B5Q/
func Solution(A []int) []int {
	n := len(A)
	max, counts := 0, make([]int, n*2+1, n*2+1) // A[i] is <= 2*N

	// calc counts and max
	for i := 0; i < n; i++ {
		counts[A[i]]++

		if max < A[i] {
			max = A[i]
		}
	}

	// Sieve of 'max' also helps us to count the number of
	// all the divisors of all the numbers upto and including 'max'
	divs := make([]int, max+1, max+1)
	for i := 2; i*i <= max; i++ {
		for j := i * i; j <= max; j += i {
			// sum of counts of divisors (excludes 1's and number itself)
			divs[j] += counts[i]
			if j/i != i {
				divs[j] += counts[j/i]
			}
		}
	}

	// calc the non-divisors
	res := make([]int, n, n)
	for i := 0; i < n; i++ {
		a := A[i]
		// discount the counts of number itself
		res[i] = n - (divs[a] + counts[a])
		// also discount the counts of 1's
		if a != 1 {
			res[i] -= counts[1]
		}
	}

	return res
}

Analysis

expand all Example tests

▶

example
example test

✔

0.001 s

Code: 19:17:18 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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

package solution

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

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

func SqrtInt(n int) int {
	return int(math.Sqrt(float64(n)))
}

// PREVIOUS RESULT: https://app.codility.com/demo/results/trainingNW9MNY-B5Q/
func Solution(A []int) []int {
	n := len(A)
	max, counts := 0, make([]int, n*2+1, n*2+1) // A[i] is <= 2*N

	// calc counts and max
	for i := 0; i < n; i++ {
		counts[A[i]]++

		if max < A[i] {
			max = A[i]
		}
	}

	// Sieve of 'max' also helps us to count the number of
	// all the divisors of all the numbers upto and including 'max'
	divs := make([]int, max+1, max+1)
	for i := 2; i*i <= max; i++ {
		for j := i * i; j <= max; j += i {
			// sum of counts of divisors (excludes 1's and number itself)
			divs[j] += counts[i]
			if j/i != i {
				divs[j] += counts[j/i]
			}
		}
	}

	// calc the non-divisors
	res := make([]int, n, n)
	for i := 0; i < n; i++ {
		a := A[i]
		// discount the counts of number itself
		res[i] = n - (divs[a] + counts[a])
		// also discount the counts of 1's
		if a != 1 {
			res[i] -= counts[1]
		}
	}

	return res
}

Analysis

expand all Example tests

▶

example
example test

✔

0.001 s

Code: 19:17:20 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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

package solution

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

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

func SqrtInt(n int) int {
	return int(math.Sqrt(float64(n)))
}

// PREVIOUS RESULT: https://app.codility.com/demo/results/trainingNW9MNY-B5Q/
func Solution(A []int) []int {
	n := len(A)
	max, counts := 0, make([]int, n*2+1, n*2+1) // A[i] is <= 2*N

	// calc counts and max
	for i := 0; i < n; i++ {
		counts[A[i]]++

		if max < A[i] {
			max = A[i]
		}
	}

	// Sieve of 'max' also helps us to count the number of
	// all the divisors of all the numbers upto and including 'max'
	divs := make([]int, max+1, max+1)
	for i := 2; i*i <= max; i++ {
		for j := i * i; j <= max; j += i {
			// sum of counts of divisors (excludes 1's and number itself)
			divs[j] += counts[i]
			if j/i != i {
				divs[j] += counts[j/i]
			}
		}
	}

	// calc the non-divisors
	res := make([]int, n, n)
	for i := 0; i < n; i++ {
		a := A[i]
		// discount the counts of number itself
		res[i] = n - (divs[a] + counts[a])
		// also discount the counts of 1's
		if a != 1 {
			res[i] -= counts[1]
		}
	}

	return res
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N * log(N))

expand all Example tests

▶

example
example test

✔

0.001 s

expand all Correctness tests

▶

extreme_simple
extreme simple

✔

0.001 s

▶

double
two elements

✔

0.001 s

▶

simple
simple tests

✔

0.001 s

▶

primes
prime numbers

✔

0.001 s

▶

small_random
small, random numbers, length = 100

✔

0.001 s

expand all Performance tests

▶

medium_random
medium, random numbers length = 5,000

✔

0.004 s

0.001 s

▶

large_range
1, 2, ..., N, length = ~20,000

✔

0.008 s

▶

large_random
large, random numbers, length = ~30,000

✔

0.016 s

▶

large_extreme
large, all the same values, length = 50,000

✔

0.028 s

0.008 s

0.012 s