# CountNonDivisible

First let’s construct an object named count, containing our numbers as keys, and number of their occurrences as values. It’s a simple optimization that can save us a lot of processing power.

Next, for each key, let’s find the number of divisors, and then simply subtract that number from the length of our initial array.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
function solution(A) { var len = A.length, max = Math.max.apply( null, A ); var count = {}; for( var i = 0; i < len; i++ ){ count[A[i]] ? count[A[i]] += 1 : count[ A[i] ] = 1; } var divisors={}; for( var key in count ){ divisors[ key ] ? divisors[ key ] += count[ key ] : divisors[ key ] = count[ key ]; var i = 2; while( i * key <= max ){ var k = i * key; if( count[k] ){ divisors[ k ] ? divisors[ k ] += count[ key ] : divisors[ k ] = count[key]; } i++; } } var res=[]; for( var i = 0; i < len; i++ ){ res.push( len - divisors[ A[ i ] ] ); } return res; } |

You are given a non-empty zero-indexed 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] = 6

For 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[6] = 6, there aren’t any non-divisors.

Write a function:

function solution(A);

that, given a non-empty zero-indexed array A consisting of N integers, returns a sequence of integers representing the amount of non-divisors.

The sequence should be returned as:

a structure Results (in C), or

a vector of integers (in C++), or

a record Results (in Pascal), or

an array of integers (in any other programming language).

For example, given:

A[0] = 3

A[1] = 1

A[2] = 2

A[3] = 3

A[4] = 6

the function should return [2, 4, 3, 2, 0], as explained above.

Assume that:

N is an integer within the range [1..50,000];

each element of array A is an integer within the range [1..2 * N].

Complexity:

expected worst-case time complexity is O(N*log(N));

expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.