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

66%

Correctness

100%

Performance

25%

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 1 minutes

Notes

not defined yet

Code: 06:43:06 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: 06:43:11 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: 06:43:21 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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110

package solution

type Element struct {
	index            []int
	count            int
	nonDivisorsCount int
}

func Solution(A []int) []int {
	lenA := len(A)

	// remove duplicates
	mapA := uniqueMap(A)

	for k, v := range mapA {

		/**
		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.

		E C ND
		1 1 0
		2 1 0
		3 2 0
		6 1 0
		*/

		// loop through all the elements.
		// calculate non divisors.
		for i := 0; i < lenA; i++ {

			if A[i] < k && k%A[i] != 0 {
				v.nonDivisorsCount++

			} else if A[i] > k {
				v.nonDivisorsCount++
			}
		}
	}

	for i := 0; i < lenA; i++ {
		if v, e := mapA[A[i]]; e {
			A[i] = v.nonDivisorsCount
		}
	}

	return A
}

// Returns map of elements with element property
func uniqueMap(A []int) map[int]*Element {
	uniqueNum := map[int]*Element{}

	for k, a := range A {

		if _, ok := uniqueNum[a]; !ok {
			uniqueNum[a] = &Element{[]int{k}, 1, 0}
		} else {
			uniqueNum[a].count = uniqueNum[a].count + 1
			uniqueNum[a].index = append(uniqueNum[a].index, k)
			// uniqueNum[a] = element{count, 0}
		}

	}

	return uniqueNum
}

/**
Previous logic before creating uniqueMap()

i := 1
	for i < lenA {

		nonDivisorsCount := 0

		if i != lenA-1 {

			if copyA[i] != copyA[i+1] {

				//check if the number already exists in map
				if _, exists := mapA[copyA[i]]; !exists {

					mapA[copyA[i]] = 0

					// check previous numbers divide i
					for j := i - 1; j >= 0; j-- {

						if copyA[i]%copyA[j] != 0 {
							nonDivisorsCount++
						}
					}

					mapA[copyA[i]] += lenA - (1 + i + nonDivisorsCount)
				}
			}
		}
		i++
	}

	for k, a := range A {
		A[k] = mapA[a]
	}

	return A
*/

Analysis

expand all Example tests

▶

example
example test

✔

0.001 s

Code: 06:43:25 UTC, go, verify, result: Passed

show code in pop-up

package solution

type Element struct {
	index            []int
	count            int
	nonDivisorsCount int
}

func Solution(A []int) []int {
	lenA := len(A)

	// remove duplicates
	mapA := uniqueMap(A)

	for k, v := range mapA {

		/**
		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.

		E C ND
		1 1 0
		2 1 0
		3 2 0
		6 1 0
		*/

		// loop through all the elements.
		// calculate non divisors.
		for i := 0; i < lenA; i++ {

			if A[i] < k && k%A[i] != 0 {
				v.nonDivisorsCount++

			} else if A[i] > k {
				v.nonDivisorsCount++
			}
		}
	}

	for i := 0; i < lenA; i++ {
		if v, e := mapA[A[i]]; e {
			A[i] = v.nonDivisorsCount
		}
	}

	return A
}

// Returns map of elements with element property
func uniqueMap(A []int) map[int]*Element {
	uniqueNum := map[int]*Element{}

	for k, a := range A {

		if _, ok := uniqueNum[a]; !ok {
			uniqueNum[a] = &Element{[]int{k}, 1, 0}
		} else {
			uniqueNum[a].count = uniqueNum[a].count + 1
			uniqueNum[a].index = append(uniqueNum[a].index, k)
			// uniqueNum[a] = element{count, 0}
		}

	}

	return uniqueNum
}

/**
Previous logic before creating uniqueMap()

i := 1
	for i < lenA {

		nonDivisorsCount := 0

		if i != lenA-1 {

			if copyA[i] != copyA[i+1] {

				//check if the number already exists in map
				if _, exists := mapA[copyA[i]]; !exists {

					mapA[copyA[i]] = 0

					// check previous numbers divide i
					for j := i - 1; j >= 0; j-- {

						if copyA[i]%copyA[j] != 0 {
							nonDivisorsCount++
						}
					}

					mapA[copyA[i]] += lenA - (1 + i + nonDivisorsCount)
				}
			}
		}
		i++
	}

	for k, a := range A {
		A[k] = mapA[a]
	}

	return A
*/

Analysis

expand all Example tests

▶

example
example test

✔

0.001 s

Code: 06:43:28 UTC, go, final, score: 66

show code in pop-up

package solution

type Element struct {
	index            []int
	count            int
	nonDivisorsCount int
}

func Solution(A []int) []int {
	lenA := len(A)

	// remove duplicates
	mapA := uniqueMap(A)

	for k, v := range mapA {

		/**
		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.

		E C ND
		1 1 0
		2 1 0
		3 2 0
		6 1 0
		*/

		// loop through all the elements.
		// calculate non divisors.
		for i := 0; i < lenA; i++ {

			if A[i] < k && k%A[i] != 0 {
				v.nonDivisorsCount++

			} else if A[i] > k {
				v.nonDivisorsCount++
			}
		}
	}

	for i := 0; i < lenA; i++ {
		if v, e := mapA[A[i]]; e {
			A[i] = v.nonDivisorsCount
		}
	}

	return A
}

// Returns map of elements with element property
func uniqueMap(A []int) map[int]*Element {
	uniqueNum := map[int]*Element{}

	for k, a := range A {

		if _, ok := uniqueNum[a]; !ok {
			uniqueNum[a] = &Element{[]int{k}, 1, 0}
		} else {
			uniqueNum[a].count = uniqueNum[a].count + 1
			uniqueNum[a].index = append(uniqueNum[a].index, k)
			// uniqueNum[a] = element{count, 0}
		}

	}

	return uniqueNum
}

/**
Previous logic before creating uniqueMap()

i := 1
	for i < lenA {

		nonDivisorsCount := 0

		if i != lenA-1 {

			if copyA[i] != copyA[i+1] {

				//check if the number already exists in map
				if _, exists := mapA[copyA[i]]; !exists {

					mapA[copyA[i]] = 0

					// check previous numbers divide i
					for j := i - 1; j >= 0; j-- {

						if copyA[i]%copyA[j] != 0 {
							nonDivisorsCount++
						}
					}

					mapA[copyA[i]] += lenA - (1 + i + nonDivisorsCount)
				}
			}
		}
		i++
	}

	for k, a := range A {
		A[k] = mapA[a]
	}

	return A
*/

Analysis summary

The following issues have been detected: timeout errors.

Analysis

Detected time complexity:

O(N ** 2)

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

✘

TIMEOUT ERROR
running time: 0.184 sec., time limit: 0.100 sec.

0.184 s

TIMEOUT ERROR, running time: 0.184 sec., time limit: 0.100 sec.

0.044 s

▶

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

✘

TIMEOUT ERROR
running time: 3.648 sec., time limit: 0.100 sec.

3.648 s

TIMEOUT ERROR, running time: 3.648 sec., time limit: 0.100 sec.

0.008 s

▶

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

✘

TIMEOUT ERROR
Killed. Hard limit reached: 6.000 sec.

6.000 s

TIMEOUT ERROR, Killed. Hard limit reached: 6.000 sec.

0.044 s

▶

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

✔

0.020 s

0.012 s

0.016 s