Skip to content

Codility – count not divisible problem

May 16, 2018

I like this solution, as it came out simple and elegant. The solution is based on Sieve of Eratosthenes. A variation actually, as had to build only based on numbers available.

package solution

// you can also use imports, for example:
//import “fmt”

// import “os”
//import “sort”

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

N := len(A)

mymap := make(map[int]int)
for i := 0; i < N; i++ {
_, ok := mymap[A[i]]
if !ok {
mymap[A[i]] = 1
} else {
mymap[A[i]] += 1
}
}

// construct a custom Eratosthenes sieve
// of factors
// Note we create a custom sieve based on numbers we have
// in the map created above
sieve := make([]int, 2*N+1)
for i := 1; i <= 2*N; i++ {
v, ok := mymap[i]
if ok {
for k := i; k <= 2*N; k += i {
sieve[k] += v
}
}
}

// Now we have every thing computed in the sieve,
// with the help of the sieve.
// We just loop again,
// and return the values from the sive

ret := make([]int, N)
for i := 0; i < N; i++ {
ret[i] = N – sieve[A[i]]
}

return ret

}

And yes, this too got 100% result. Yay!
codility-count-not-divisible

Advertisements

From → Uncategorized

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: