Calculate the number of elements of an array that are not divisors of each element.
- Difficulty Level: Medium
- Question URL: https://app.codility.com/programmers/lessons/11-sieve_of_eratosthenes/count_non_divisible/
- Time Complexity:
Solution:
Solution to Codility's Count Non Divisible problem which is from the Codility Lesson 11: Sieve of Eratosthenes and, is solved in Java 8 with 100% performance and correctness scores. The goal here is to calculate the number of elements of an array that are not divisors of each element. You can find the question of this CountNonDivisible problem in the Codility website.
package Codility.Lesson11;
import java.util.*;
public class CountNonDivisible {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a1 = { 3, 1, 2, 3, 6 };
int result2[] = solution(a1);
System.out.println(Arrays.toString(result2));
}
public static int[] solution(int[] A) {
// write your code in Java SE 8
int[][] bucket = new int[A.length * 2 + 1][2];
// bucket sorting
for (int a : A) {
bucket[a][0]++; // remember how many the number "A[i]" in A
bucket[a][1] = -1; // divisors initialized
}
// System.out.println("=="+Arrays.toString(bucket)+"==");
for (int a : A) {
if (bucket[a][1] == -1) {
bucket[a][1] = 0;
// get all divisors of the integer A[i]
for (int j = 1; j * j <= a; j++) {
if (a % j == 0 && a / j != j) {
bucket[a][1] += bucket[j][0];//Factorization: j
bucket[a][1] += bucket[a / j][0]; //Factorization: element/j
} else if (a % j == 0 && a / j == j) {
bucket[a][1] += bucket[j][0];
}
}
}
}
// using array A to set results for not arranging new space
for (int i = 0; i < A.length; i++) {
A[i] = A.length - bucket[A[i]][1];
}
return A;
}
}