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!

From → Uncategorized