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] = 6For 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:
class Solution { public int[] solution(int[] A); }
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] = 6the 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].
// you can also use imports, for example:
// import java.math.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
// Solution for Lesson 9, "CountNonDivisible"
// of http://codility.com/demo/train/
public class Solution
{
public int[] solution(int[] A)
{
Set<Integer> setA = asSet(A);
List<Set<Integer>> divisors = computeDivisors(A.length * 2);
int occurrences[] = computeOccurrences(A);
int nonDivisors[] = new int[A.length];
for (int i=0; i<A.length; i++)
{
int value = A[i];
Set<Integer> d = divisors.get(value);
int totalOccurances = 0;
for (Integer divisor : d)
{
if (setA.contains(divisor))
{
totalOccurances += occurrences[divisor];
}
}
nonDivisors[i] = A.length-totalOccurances;
}
return nonDivisors;
}
/**
* Returns a set containing all elements of the given array
*
* Space: O(N)
* Time: O(N)
*
* @param A The input array
* @return The set
*/
private static Set<Integer> asSet(int A[])
{
Set<Integer> result = new HashSet<Integer>();
for (int value : A)
{
result.add(value);
}
return result;
}
/**
* Computes a list that contains for each i in [0...maxValue+1] a set
* with all divisors of i. This is basically an "Eratosthenes Sieve".
* But in addition to setting the entries of a list to 'false'
* (indicating that the respective numbers are non-prime), this
* methods inserts the divisors into the corresponding set.
*
* Space: O(N) (?)
* Time: O(N*logN)
*
* @param maxValue The maximum value
* @return The list
*/
private static List<Set<Integer>> computeDivisors(int maxValue)
{
List<Boolean> prime = new ArrayList<Boolean>();
prime.addAll(Collections.nCopies(maxValue+1, Boolean.TRUE));
List<Set<Integer>> divisors = new ArrayList<Set<Integer>>();
for (int i = 0; i < maxValue + 1; i++)
{
Set<Integer> d = new HashSet<Integer>();
d.add(1);
d.add(i);
divisors.add(d);
}
for (int i = 2; i * i <= maxValue; i++)
{
if (prime.get(i))
{
int next = i + i;
while (next <= maxValue)
{
divisors.get(next).add(i);
prime.set(next, Boolean.FALSE);
next += i;
}
}
}
return divisors;
}
/**
* Computes an array of length 2*A.length, where each entry i contains
* the number of occurrences of value i in array A
*
* Space: O(N)
* Time: O(N)
*
* @param A The input array
* @return The occurrences array
*/
private static int[] computeOccurrences(int A[])
{
int occurances[] = new int[A.length * 2];
for (int i=0; i<A.length; i++)
{
int value = A[i];
occurances[value]++;
}
return occurances;
}
}
// you can also use imports, for example:
// import java.math.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
// Solution for Lesson 9, "CountNonDivisible"
// of http://codility.com/demo/train/
public class Solution
{
public int[] solution(int[] A)
{
Set<Integer> setA = asSet(A);
List<Set<Integer>> divisors = computeDivisors(A.length * 2);
int occurrences[] = computeOccurrences(A);
int nonDivisors[] = new int[A.length];
for (int i=0; i<A.length; i++)
{
int value = A[i];
Set<Integer> d = divisors.get(value);
int totalOccurances = 0;
for (Integer divisor : d)
{
if (setA.contains(divisor))
{
totalOccurances += occurrences[divisor];
}
}
nonDivisors[i] = A.length-totalOccurances;
}
return nonDivisors;
}
/**
* Returns a set containing all elements of the given array
*
* Space: O(N)
* Time: O(N)
*
* @param A The input array
* @return The set
*/
private static Set<Integer> asSet(int A[])
{
Set<Integer> result = new HashSet<Integer>();
for (int value : A)
{
result.add(value);
}
return result;
}
/**
* Computes a list that contains for each i in [0...maxValue+1] a set
* with all divisors of i. This is basically an "Eratosthenes Sieve".
* But in addition to setting the entries of a list to 'false'
* (indicating that the respective numbers are non-prime), this
* methods inserts the divisors into the corresponding set.
*
* Space: O(N) (?)
* Time: O(N*logN)
*
* @param maxValue The maximum value
* @return The list
*/
private static List<Set<Integer>> computeDivisors(int maxValue)
{
List<Boolean> prime = new ArrayList<Boolean>();
prime.addAll(Collections.nCopies(maxValue+1, Boolean.TRUE));
List<Set<Integer>> divisors = new ArrayList<Set<Integer>>();
for (int i = 0; i < maxValue + 1; i++)
{
Set<Integer> d = new HashSet<Integer>();
d.add(1);
d.add(i);
divisors.add(d);
}
for (int i = 2; i * i <= maxValue; i++)
{
if (prime.get(i))
{
int next = i + i;
while (next <= maxValue)
{
divisors.get(next).add(i);
prime.set(next, Boolean.FALSE);
next += i;
}
}
}
return divisors;
}
/**
* Computes an array of length 2*A.length, where each entry i contains
* the number of occurrences of value i in array A
*
* Space: O(N)
* Time: O(N)
*
* @param A The input array
* @return The occurrences array
*/
private static int[] computeOccurrences(int A[])
{
int occurances[] = new int[A.length * 2];
for (int i=0; i<A.length; i++)
{
int value = A[i];
occurances[value]++;
}
return occurances;
}
}
// you can also use imports, for example:
// import java.math.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
// Solution for Lesson 9, "CountNonDivisible"
// of http://codility.com/demo/train/
public class Solution
{
public int[] solution(int[] A)
{
Set<Integer> setA = asSet(A);
List<Set<Integer>> divisors = computeDivisors(A.length * 2);
int occurrences[] = computeOccurrences(A);
int nonDivisors[] = new int[A.length];
for (int i=0; i<A.length; i++)
{
int value = A[i];
Set<Integer> d = divisors.get(value);
int totalOccurances = 0;
for (Integer divisor : d)
{
if (setA.contains(divisor))
{
totalOccurances += occurrences[divisor];
}
}
nonDivisors[i] = A.length-totalOccurances;
}
return nonDivisors;
}
/**
* Returns a set containing all elements of the given array
*
* Space: O(N)
* Time: O(N)
*
* @param A The input array
* @return The set
*/
private static Set<Integer> asSet(int A[])
{
Set<Integer> result = new HashSet<Integer>();
for (int value : A)
{
result.add(value);
}
return result;
}
/**
* Computes a list that contains for each i in [0...maxValue+1] a set
* with all divisors of i. This is basically an "Eratosthenes Sieve".
* But in addition to setting the entries of a list to 'false'
* (indicating that the respective numbers are non-prime), this
* methods inserts the divisors into the corresponding set.
*
* Space: O(N) (?)
* Time: O(N*logN)
*
* @param maxValue The maximum value
* @return The list
*/
private static List<Set<Integer>> computeDivisors(int maxValue)
{
List<Boolean> prime = new ArrayList<Boolean>();
prime.addAll(Collections.nCopies(maxValue+1, Boolean.TRUE));
List<Set<Integer>> divisors = new ArrayList<Set<Integer>>();
for (int i = 0; i < maxValue + 1; i++)
{
Set<Integer> d = new HashSet<Integer>();
d.add(1);
d.add(i);
divisors.add(d);
}
for (int i = 2; i * i <= maxValue; i++)
{
if (prime.get(i))
{
int next = i + i;
while (next <= maxValue)
{
divisors.get(next).add(i);
prime.set(next, Boolean.FALSE);
next += i;
}
}
}
return divisors;
}
/**
* Computes an array of length 2*A.length, where each entry i contains
* the number of occurrences of value i in array A
*
* Space: O(N)
* Time: O(N)
*
* @param A The input array
* @return The occurrences array
*/
private static int[] computeOccurrences(int A[])
{
int occurances[] = new int[A.length * 2];
for (int i=0; i<A.length; i++)
{
int value = A[i];
occurances[value]++;
}
return occurances;
}
}
// you can also use imports, for example:
// import java.math.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
// Solution for Lesson 9, "CountNonDivisible"
// of http://codility.com/demo/train/
public class Solution
{
public int[] solution(int[] A)
{
Set<Integer> setA = asSet(A);
List<Set<Integer>> divisors = computeDivisors(A.length * 2);
int occurrences[] = computeOccurrences(A);
int nonDivisors[] = new int[A.length];
for (int i=0; i<A.length; i++)
{
int value = A[i];
Set<Integer> d = divisors.get(value);
int totalOccurances = 0;
for (Integer divisor : d)
{
if (setA.contains(divisor))
{
totalOccurances += occurrences[divisor];
}
}
nonDivisors[i] = A.length-totalOccurances;
}
return nonDivisors;
}
/**
* Returns a set containing all elements of the given array
*
* Space: O(N)
* Time: O(N)
*
* @param A The input array
* @return The set
*/
private static Set<Integer> asSet(int A[])
{
Set<Integer> result = new HashSet<Integer>();
for (int value : A)
{
result.add(value);
}
return result;
}
/**
* Computes a list that contains for each i in [0...maxValue+1] a set
* with all divisors of i. This is basically an "Eratosthenes Sieve".
* But in addition to setting the entries of a list to 'false'
* (indicating that the respective numbers are non-prime), this
* methods inserts the divisors into the corresponding set.
*
* Space: O(N) (?)
* Time: O(N*logN)
*
* @param maxValue The maximum value
* @return The list
*/
private static List<Set<Integer>> computeDivisors(int maxValue)
{
List<Boolean> prime = new ArrayList<Boolean>();
prime.addAll(Collections.nCopies(maxValue+1, Boolean.TRUE));
List<Set<Integer>> divisors = new ArrayList<Set<Integer>>();
for (int i = 0; i < maxValue + 1; i++)
{
Set<Integer> d = new HashSet<Integer>();
d.add(1);
d.add(i);
divisors.add(d);
}
for (int i = 2; i * i <= maxValue; i++)
{
if (prime.get(i))
{
int next = i + i;
while (next <= maxValue)
{
divisors.get(next).add(i);
prime.set(next, Boolean.FALSE);
next += i;
}
}
}
return divisors;
}
/**
* Computes an array of length 2*A.length, where each entry i contains
* the number of occurrences of value i in array A
*
* Space: O(N)
* Time: O(N)
*
* @param A The input array
* @return The occurrences array
*/
private static int[] computeOccurrences(int A[])
{
int occurances[] = new int[A.length * 2];
for (int i=0; i<A.length; i++)
{
int value = A[i];
occurances[value]++;
}
return occurances;
}
}
// you can also use imports, for example:
// import java.math.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
// Solution for Lesson 9, "CountNonDivisible"
// of http://codility.com/demo/train/
public class Solution
{
public int[] solution(int[] A)
{
Set<Integer> setA = asSet(A);
List<Set<Integer>> divisors = computeDivisors(A.length * 2);
int occurrences[] = computeOccurrences(A);
int nonDivisors[] = new int[A.length];
for (int i=0; i<A.length; i++)
{
int value = A[i];
Set<Integer> d = divisors.get(value);
int totalOccurances = 0;
for (Integer divisor : d)
{
if (setA.contains(divisor))
{
totalOccurances += occurrences[divisor];
}
}
nonDivisors[i] = A.length-totalOccurances;
}
return nonDivisors;
}
/**
* Returns a set containing all elements of the given array
*
* Space: O(N)
* Time: O(N)
*
* @param A The input array
* @return The set
*/
private static Set<Integer> asSet(int A[])
{
Set<Integer> result = new HashSet<Integer>();
for (int value : A)
{
result.add(value);
}
return result;
}
/**
* Computes a list that contains for each i in [0...maxValue+1] a set
* with all divisors of i. This is basically an "Eratosthenes Sieve".
* But in addition to setting the entries of a list to 'false'
* (indicating that the respective numbers are non-prime), this
* methods inserts the divisors into the corresponding set.
*
* Space: O(N) (?)
* Time: O(N*logN)
*
* @param maxValue The maximum value
* @return The list
*/
private static List<Set<Integer>> computeDivisors(int maxValue)
{
List<Boolean> prime = new ArrayList<Boolean>();
prime.addAll(Collections.nCopies(maxValue+1, Boolean.TRUE));
List<Set<Integer>> divisors = new ArrayList<Set<Integer>>();
for (int i = 0; i < maxValue + 1; i++)
{
Set<Integer> d = new HashSet<Integer>();
d.add(1);
d.add(i);
divisors.add(d);
}
for (int i = 2; i * i <= maxValue; i++)
{
if (prime.get(i))
{
int next = i + i;
while (next <= maxValue)
{
divisors.get(next).add(i);
prime.set(next, Boolean.FALSE);
next += i;
}
}
}
return divisors;
}
/**
* Computes an array of length 2*A.length, where each entry i contains
* the number of occurrences of value i in array A
*
* Space: O(N)
* Time: O(N)
*
* @param A The input array
* @return The occurrences array
*/
private static int[] computeOccurrences(int A[])
{
int occurances[] = new int[A.length * 2];
for (int i=0; i<A.length; i++)
{
int value = A[i];
occurances[value]++;
}
return occurances;
}
}
// you can also use imports, for example:
// import java.math.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
// Solution for Lesson 9, "CountNonDivisible"
// of http://codility.com/demo/train/
public class Solution
{
public int[] solution(int[] A)
{
Set<Integer> setA = asSet(A);
List<Set<Integer>> divisors = computeDivisors(A.length * 2);
int occurrences[] = computeOccurrences(A);
int nonDivisors[] = new int[A.length];
for (int i=0; i<A.length; i++)
{
int value = A[i];
Set<Integer> d = divisors.get(value);
int totalOccurances = 0;
for (Integer divisor : d)
{
if (setA.contains(divisor))
{
totalOccurances += occurrences[divisor];
}
}
nonDivisors[i] = A.length-totalOccurances;
}
return nonDivisors;
}
/**
* Returns a set containing all elements of the given array
*
* Space: O(N)
* Time: O(N)
*
* @param A The input array
* @return The set
*/
private static Set<Integer> asSet(int A[])
{
Set<Integer> result = new HashSet<Integer>();
for (int value : A)
{
result.add(value);
}
return result;
}
/**
* Computes a list that contains for each i in [0...maxValue+1] a set
* with all divisors of i. This is basically an "Eratosthenes Sieve".
* But in addition to setting the entries of a list to 'false'
* (indicating that the respective numbers are non-prime), this
* methods inserts the divisors into the corresponding set.
*
* Space: O(N) (?)
* Time: O(N*logN)
*
* @param maxValue The maximum value
* @return The list
*/
private static List<Set<Integer>> computeDivisors(int maxValue)
{
List<Boolean> prime = new ArrayList<Boolean>();
prime.addAll(Collections.nCopies(maxValue+1, Boolean.TRUE));
List<Set<Integer>> divisors = new ArrayList<Set<Integer>>();
for (int i = 0; i < maxValue + 1; i++)
{
Set<Integer> d = new HashSet<Integer>();
d.add(1);
d.add(i);
divisors.add(d);
}
for (int i = 2; i * i <= maxValue; i++)
{
if (prime.get(i))
{
int next = i + i;
while (next <= maxValue)
{
divisors.get(next).add(i);
prime.set(next, Boolean.FALSE);
next += i;
}
}
}
return divisors;
}
/**
* Computes an array of length 2*A.length, where each entry i contains
* the number of occurrences of value i in array A
*
* Space: O(N)
* Time: O(N)
*
* @param A The input array
* @return The occurrences array
*/
private static int[] computeOccurrences(int A[])
{
int occurances[] = new int[A.length * 2];
for (int i=0; i<A.length; i++)
{
int value = A[i];
occurances[value]++;
}
return occurances;
}
}
The following issues have been detected: wrong answers, runtime errors.
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2 at Solution.computeOccurrences(Solution.java:116) at Solution.solution(Solution.java:20) at wrapper.run(wrapper.java:27) at wrapper.main(wrapper.java:20)
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 4 at Solution.computeOccurrences(Solution.java:116) at Solution.solution(Solution.java:20) at wrapper.run(wrapper.java:27) at wrapper.main(wrapper.java:20)
small, random numbers, length = 100
tested program terminated unexpectedly
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 200 at Solution.computeOccurrences(Solution.java:116) at Solution.solution(Solution.java:20) at wrapper.run(wrapper.java:27) at wrapper.main(wrapper.java:20)
medium, random numbers length = 5,000
got [4995, 4995, 4996, 4.. expected [4994, 4989, 4995, 4..
1, 2, ..., N, length = ~20,000
got [19994, 19996, 19995.. expected [19984, 19992, 19968..
large, random numbers, length = ~30,000
got [29996, 29994, 29999.. expected [29996, 29989, 29999..
large, all the same values, length = 50,000
tested program terminated unexpectedly
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 100000 at Solution.computeOccurrences(Solution.java:116) at Solution.solution(Solution.java:20) at wrapper.run(wrapper.java:27) at wrapper.main(wrapper.java:20)