Tasks Details
medium
Calculate the number of elements of an array that are not divisors of each element.
Task Score
100%
Correctness
100%
Performance
100%
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].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 8
Time spent on task 10 minutes
Notes
not defined yet
Code: 07:43:15 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] A) {
Map<Integer,List<Integer>> divisorsOf = new HashMap<Integer,List<Integer>>();
Map<Integer,Integer> countOf = new HashMap<Integer,Integer>();
// calc counts and divisors
final int N = A.length;
for( int a : A ) {
Integer newCount = 1;
if( countOf.containsKey( a ) ) {
newCount = countOf.get( a ) + 1;
} else {
// Calc divisors only once
List<Integer> divisors = new ArrayList<Integer>();
final int sqrtA = (int)Math.sqrt(a);
for( int i = 1; i <= sqrtA; ++i ) {
if( 0 == a%i ) {
divisors.add( i );
if( i * i != a ) divisors.add( a/i ); // count it once
}
}
divisorsOf.put( a, divisors );
}
countOf.put( a, newCount );
}
List<Integer> result = new ArrayList<Integer>();
for( int a : A ) {
int nNonDivisors = N;
for( int d : divisorsOf.get( a ) ) {
nNonDivisors -= countOf.get( d );
}
result.add( nNonDivisors );
}
return toIntArray( result );
}
private int[] toIntArray( List<Integer> list ) {
int[] result = new int[ list.size() ];
for( int i = 0; i < result.length; ++i ) {
result[i] = list.get( i );
}
return result;
}
}
User test case 1:
None
User test case 2:
None
Analysis
expand all
User tests
1.
1.248 s
OK
function result: [0]
function result: [0]
1.
1.152 s
OK
function result: [3, 2, 1, 0]
function result: [3, 2, 1, 0]
Code: 07:44:31 UTC,
java,
verify,
result: Passed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] A) {
Map<Integer,List<Integer>> divisorsOf = new HashMap<Integer,List<Integer>>();
Map<Integer,Integer> countOf = new HashMap<Integer,Integer>();
// calc counts and divisors
final int N = A.length;
for( int a : A ) {
Integer newCount = 1;
if( countOf.containsKey( a ) ) {
newCount = countOf.get( a ) + 1;
} else {
// Calc divisors only once
List<Integer> divisors = new ArrayList<Integer>();
final int sqrtA = (int)Math.sqrt(a);
for( int i = 1; i <= sqrtA; ++i ) {
if( 0 == a%i ) {
divisors.add( i );
if( i * i != a ) divisors.add( a/i ); // count it once
}
}
divisorsOf.put( a, divisors );
}
countOf.put( a, newCount );
}
System.out.println(countOf);
System.out.println(divisorsOf);
List<Integer> result = new ArrayList<Integer>();
for( int a : A ) {
int nNonDivisors = N;
for( int d : divisorsOf.get( a ) ) {
nNonDivisors -= countOf.get( d );
}
result.add( nNonDivisors );
}
return toIntArray( result );
}
private int[] toIntArray( List<Integer> list ) {
int[] result = new int[ list.size() ];
for( int i = 0; i < result.length; ++i ) {
result[i] = list.get( i );
}
return result;
}
}
User test case 1:
None
User test case 2:
None
Analysis
expand all
Example tests
1.
1.288 s
OK
stdout:
WARNING: producing output may seriously slow down your code!
{1=1, 2=1, 3=2, 6=1}
{1=[1], 2=[1, 2], 3=[1, 3], 6=[1, 6, 2, 3]}
expand all
User tests
1.
1.268 s
OK
function result: [0]
function result: [0]
stdout:
WARNING: producing output may seriously slow down your code!
{1=1}
{1=[1]}
1.
1.288 s
OK
function result: [3, 2, 1, 0]
function result: [3, 2, 1, 0]
stdout:
WARNING: producing output may seriously slow down your code!
{1=1, 2=1, 4=1, 8=1}
{1=[1], 2=[1, 2], 4=[1, 4, 2], 8=[1, 8, 2, 4]}
Code: 07:46:02 UTC,
java,
verify,
result: Passed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] A) {
Map<Integer,List<Integer>> divisorsOf = new HashMap<Integer,List<Integer>>();
Map<Integer,Integer> countOf = new HashMap<Integer,Integer>();
// calc counts and divisors
final int N = A.length;
for( int a : A ) {
Integer newCount = 1;
if( countOf.containsKey( a ) ) {
newCount = countOf.get( a ) + 1;
} else {
// Calc divisors only once
List<Integer> divisors = new ArrayList<Integer>();
final int sqrtA = (int)Math.sqrt(a);
for( int i = 1; i <= sqrtA; ++i ) {
if( 0 == a%i ) {
divisors.add( i );
if( i * i != a ) divisors.add( a/i ); // count it once
}
}
divisorsOf.put( a, divisors );
}
countOf.put( a, newCount );
}
System.out.println(countOf);
System.out.println(divisorsOf);
List<Integer> result = new ArrayList<Integer>();
for( int a : A ) {
int nNonDivisors = N;
for( int d : divisorsOf.get( a ) ) {
nNonDivisors -= countOf.get( d );
}
result.add( nNonDivisors );
}
return toIntArray( result );
}
private int[] toIntArray( List<Integer> list ) {
int[] result = new int[ list.size() ];
for( int i = 0; i < result.length; ++i ) {
result[i] = list.get( i );
}
return result;
}
}
User test case 1:
None
User test case 2:
None
User test case 3:
None
User test case 4:
None
Analysis
expand all
Example tests
1.
1.264 s
OK
stdout:
WARNING: producing output may seriously slow down your code!
{1=1, 2=1, 3=2, 6=1}
{1=[1], 2=[1, 2], 3=[1, 3], 6=[1, 6, 2, 3]}
expand all
User tests
1.
1.292 s
OK
function result: [0]
function result: [0]
stdout:
WARNING: producing output may seriously slow down your code!
{1=1}
{1=[1]}
1.
1.276 s
OK
function result: [3, 2, 1, 0]
function result: [3, 2, 1, 0]
stdout:
WARNING: producing output may seriously slow down your code!
{1=1, 2=1, 4=1, 8=1}
{1=[1], 2=[1, 2], 4=[1, 4, 2], 8=[1, 8, 2, 4]}
1.
1.268 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
{1=1, 2=1, 50=1, 3=1, 4=1, 5=1, 120=1, 12=1}
{1=[1], 2=[1, 2], 50=[1, 50, 2, 25, 5, 10], 3=[1, 3], 4=[1, 4, 2], 5=[1, 5], 120=[1, 120, 2, 60, 3, 40, 4, 30, 5, 24, 6, 20, 8, 15, 10, 12], 12=[1, 12, 2, 6, 3, 4]}
Exception in thread "main" java.lang.NullPointerException
at Solution.solution(Solution.java:40)
at wrapper.run(wrapper.java:28)
at wrapper.main(wrapper.java:21)
1.
1.272 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
{2=1, 4=1, 8=1, 12=1}
{2=[1, 2], 4=[1, 4, 2], 8=[1, 8, 2, 4], 12=[1, 12, 2, 6, 3, 4]}
Exception in thread "main" java.lang.NullPointerException
at Solution.solution(Solution.java:40)
at wrapper.run(wrapper.java:28)
at wrapper.main(wrapper.java:21)
Code: 07:49:05 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] A) {
Map<Integer,List<Integer>> divisorsOf = new HashMap<Integer,List<Integer>>();
Map<Integer,Integer> countOf = new HashMap<Integer,Integer>();
// calc counts and divisors
final int N = A.length;
for( int a : A ) {
Integer newCount = 1;
if( countOf.containsKey( a ) ) {
newCount = countOf.get( a ) + 1;
} else {
// Calc divisors only once
List<Integer> divisors = new ArrayList<Integer>();
final int sqrtA = (int)Math.sqrt(a);
for( int i = 1; i <= sqrtA; ++i ) {
if( 0 == a%i ) {
divisors.add( i );
if( i * i != a ) divisors.add( a/i ); // count it once
}
}
divisorsOf.put( a, divisors );
}
countOf.put( a, newCount );
}
System.out.println(countOf);
System.out.println(divisorsOf);
List<Integer> result = new ArrayList<Integer>();
for( int a : A ) {
int nNonDivisors = N;
for( int d : divisorsOf.get( a ) ) {
anyD = countOf.get( d );
if( anyD != null ) nNonDivisors -= anyD;
}
result.add( nNonDivisors );
}
return toIntArray( result );
}
private int[] toIntArray( List<Integer> list ) {
int[] result = new int[ list.size() ];
for( int i = 0; i < result.length; ++i ) {
result[i] = list.get( i );
}
return result;
}
}
Analysis
Compile error
Solution.java:40: error: cannot find symbol
anyD = countOf.get( d );
^
symbol: variable anyD
location: class Solution
Solution.java:41: error: cannot find symbol
if( anyD != null ) nNonDivisors -= anyD;
^
symbol: variable anyD
location: class Solution
Solution.java:41: error: cannot find symbol
if( anyD != null ) nNonDivisors -= anyD;
^
symbol: variable anyD
location: class Solution
3 errors
Code: 07:50:57 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] A) {
Map<Integer,List<Integer>> divisorsOf = new HashMap<Integer,List<Integer>>();
Map<Integer,Integer> countOf = new HashMap<Integer,Integer>();
// calc counts and divisors
final int N = A.length;
for( int a : A ) {
Integer newCount = 1;
if( countOf.containsKey( a ) ) {
newCount = countOf.get( a ) + 1;
} else {
// Calc divisors only once
List<Integer> divisors = new ArrayList<Integer>();
final int sqrtA = (int)Math.sqrt(a);
for( int i = 1; i <= sqrtA; ++i ) {
if( 0 == a%i ) {
divisors.add( i );
if( i * i != a ) divisors.add( a/i ); // count it once
}
}
divisorsOf.put( a, divisors );
}
countOf.put( a, newCount );
}
System.out.println(countOf);
System.out.println(divisorsOf);
List<Integer> result = new ArrayList<Integer>();
for( int a : A ) {
int nNonDivisors = N;
for( int d : divisorsOf.get( a ) ) {
Integer anyD = countOf.get( d );
if( anyD != null ) nNonDivisors -= anyD;
}
result.add( nNonDivisors );
}
return toIntArray( result );
}
private int[] toIntArray( List<Integer> list ) {
int[] result = new int[ list.size() ];
for( int i = 0; i < result.length; ++i ) {
result[i] = list.get( i );
}
return result;
}
}
User test case 1:
None
User test case 2:
None
User test case 3:
None
User test case 4:
None
Analysis
expand all
Example tests
1.
1.208 s
OK
stdout:
WARNING: producing output may seriously slow down your code!
{1=1, 2=1, 3=2, 6=1}
{1=[1], 2=[1, 2], 3=[1, 3], 6=[1, 6, 2, 3]}
expand all
User tests
1.
1.300 s
OK
function result: [0]
function result: [0]
stdout:
WARNING: producing output may seriously slow down your code!
{1=1}
{1=[1]}
1.
1.484 s
OK
function result: [3, 2, 1, 0]
function result: [3, 2, 1, 0]
stdout:
WARNING: producing output may seriously slow down your code!
{1=1, 2=1, 4=1, 8=1}
{1=[1], 2=[1, 2], 4=[1, 4, 2], 8=[1, 8, 2, 4]}
1.
1.576 s
OK
function result: [7, 6, 6, 5, 3, 1, 6, 4]
function result: [7, 6, 6, 5, 3, 1, 6, 4]
stdout:
WARNING: producing output may seriously slow down your code!
{1=1, 2=1, 50=1, 3=1, 4=1, 5=1, 120=1, 12=1}
{1=[1], 2=[1, 2], 50=[1, 50, 2, 25, 5, 10], 3=[1, 3], 4=[1, 4, 2], 5=[1, 5], 120=[1, 120, 2, 60, 3, 40, 4, 30, 5, 24, 6, 20, 8, 15, 10, 12], 12=[1, 12, 2, 6, 3, 4]}
1.
1.452 s
OK
function result: [2, 1, 3, 4, 4, 1]
function result: [2, 1, 3, 4, 4, 1]
stdout:
WARNING: producing output may seriously slow down your code!
{2=2, 4=1, 8=2, 12=1}
{2=[1, 2], 4=[1, 4, 2], 8=[1, 8, 2, 4], 12=[1, 12, 2, 6, 3, 4]}
Code: 07:51:40 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] A) {
Map<Integer,List<Integer>> divisorsOf = new HashMap<Integer,List<Integer>>();
Map<Integer,Integer> countOf = new HashMap<Integer,Integer>();
// calc counts and divisors
final int N = A.length;
for( int a : A ) {
Integer newCount = 1;
if( countOf.containsKey( a ) ) {
newCount = countOf.get( a ) + 1;
} else {
// Calc divisors only once
List<Integer> divisors = new ArrayList<Integer>();
final int sqrtA = (int)Math.sqrt(a);
for( int i = 1; i <= sqrtA; ++i ) {
if( 0 == a%i ) {
divisors.add( i );
if( i * i != a ) divisors.add( a/i ); // count it once
}
}
divisorsOf.put( a, divisors );
}
countOf.put( a, newCount );
}
// System.out.println(countOf);
// System.out.println(divisorsOf);
List<Integer> result = new ArrayList<Integer>();
for( int a : A ) {
int nNonDivisors = N;
for( int d : divisorsOf.get( a ) ) {
Integer anyD = countOf.get( d );
if( anyD != null ) nNonDivisors -= anyD;
}
result.add( nNonDivisors );
}
return toIntArray( result );
}
private int[] toIntArray( List<Integer> list ) {
int[] result = new int[ list.size() ];
for( int i = 0; i < result.length; ++i ) {
result[i] = list.get( i );
}
return result;
}
}
User test case 1:
None
User test case 2:
None
User test case 3:
None
User test case 4:
None
Analysis
expand all
User tests
1.
1.564 s
OK
function result: [0]
function result: [0]
1.
1.524 s
OK
function result: [3, 2, 1, 0]
function result: [3, 2, 1, 0]
1.
1.492 s
OK
function result: [7, 6, 6, 5, 3, 1, 6, 4]
function result: [7, 6, 6, 5, 3, 1, 6, 4]
1.
1.516 s
OK
function result: [2, 1, 3, 4, 4, 1]
function result: [2, 1, 3, 4, 4, 1]
Code: 07:51:58 UTC,
java,
final,
score:
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] A) {
Map<Integer,List<Integer>> divisorsOf = new HashMap<Integer,List<Integer>>();
Map<Integer,Integer> countOf = new HashMap<Integer,Integer>();
// calc counts and divisors
final int N = A.length;
for( int a : A ) {
Integer newCount = 1;
if( countOf.containsKey( a ) ) {
newCount = countOf.get( a ) + 1;
} else {
// Calc divisors only once
List<Integer> divisors = new ArrayList<Integer>();
final int sqrtA = (int)Math.sqrt(a);
for( int i = 1; i <= sqrtA; ++i ) {
if( 0 == a%i ) {
divisors.add( i );
if( i * i != a ) divisors.add( a/i ); // count it once
}
}
divisorsOf.put( a, divisors );
}
countOf.put( a, newCount );
}
// System.out.println(countOf);
// System.out.println(divisorsOf);
List<Integer> result = new ArrayList<Integer>();
for( int a : A ) {
int nNonDivisors = N;
for( int d : divisorsOf.get( a ) ) {
Integer anyD = countOf.get( d );
if( anyD != null ) nNonDivisors -= anyD;
}
result.add( nNonDivisors );
}
return toIntArray( result );
}
private int[] toIntArray( List<Integer> list ) {
int[] result = new int[ list.size() ];
for( int i = 0; i < result.length; ++i ) {
result[i] = list.get( i );
}
return result;
}
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N * log(N))