Solution to Count-Non-Divisible by codility | Code Says
Using the Sieve of Eratosthenes, you generate divisors for all input elements of A. If a given number x is a divisor of element (x*N == element), then N also is a divisor. (N = element//x). After all divisors are computed, we simply subtract those (multiplied by their counts or 0) from the total number of elements in A.
http://blog.csdn.net/liushuying668/article/details/38302693
我们可以用2 * N的空间统计数组A中每个数出现多少次。我们在用一张表tab[1..2 * N]，tab[i]记录数组A中出现的i的非约数有几个。起初我们认为tab[i] = N，即A中所有的数都不是i的约数。然后对于每个A中出现的数，类似筛法，我们求它所有的倍数j,从tab[j]中减掉i在A中出现的次数，因为i是j的约数。时间复杂度主要在筛法那里 是O(2Nlog(2N)) = O(NlogN)。空间复杂度主要是两张表，一张统计数在A出现多少次，一张是tab，因为数据范围是2 * N，所以这个空间还是O(N)的。
The simplest solution is to check the occurrences of each value first, and then when we we given a number A[i], we check the divisors of A[i], which will be between 1 and sqrt(A[i]). We count the total number of the occurrences of all the divisors (and the answers for (A[i] / divisor) ) and and subtract it from N.
This solution gives the 100% score.
However, the time complexity of the part to check a number between 1 and sqrt(A[i]) is O(sqrt(N)) , so this is indeed O(N * sqrt(N)), while the problem requires a O(N * log(N) ) solution.
The O(N * sqrt(N)) solution
struct Results solution(int A[], int N)
{
//the number that may appear will be [1 ... 2 * N].
int size = sizeof(int) * (N * 2 + 1);
int* occurrence = (int*)alloca(size);
memset(occurrence, 0x00, size);
//allocate the memory for the result.
struct Results result;
result.C = (int*)calloc(N, sizeof(int));
result.L = N;
//now we check the array A and count the occurance for each number.
int i,j;
for (i = 0; i < N; i++){
occurrence[A[i]]++;
}
//now we compute the answer.
for (i = 0; i < N; i++){
int num = A[i];
int div_cnt = 0;
//count the number of the divisor while doing factorization.
for (j = 1; j * j < num; j++){
if (num % j == 0){
div_cnt += occurrence[j];
div_cnt += occurrence[num / j];
}
};
if (j * j == num){
div_cnt += occurrence[j];
}
result.C[i] = N - div_cnt;
}
return result;
}
The O(N * log(N)) solution
struct Results solution(int A[], int N)
{
//the number that may appear will be [1 ... 2 * N].
int size = sizeof(int) * (N * 2 + 1);
int* occurrence = (int*)alloca(size);
memset(occurrence, 0x00, size);
//the space to hold the answer for each value from 1 ... 2 * N.
//for now we initialize it
int* answer = (int*)alloca(size);
memset(answer, 0x00, size);
//allocate the memory for the result.
struct Results result;
result.C = (int*)calloc(N, sizeof(int));
result.L = N;
//now we check the array A and count the occurance for each number.
int i;
for (i = 0; i < N; i++){
occurrence[A[i]]++;
}
//now we compute the answer.
for (i = 1; i <= N * 2; i++){
int num = occurrence[i];
//the number doesn't in the array A, we can neglect it.
if (num == 0){
continue;
}
//if it appears in the array A,
//subtract its counts from cells at itss multiples in the answer array.
int j;
for (j = i; j <= N * 2; j += i){
answer[j] -= num;
}
}
//as the answer array contains the offset to N,
//N + answer[A[i]] will give the answer for each.
for (i = 0; i < N; i++){
result.C[i] = N + answer[A[i]];
}
return result;
}
http://codesays.com/2014/solution-to-count-non-divisible-by-codility/
Read full article from Solution to Count-Non-Divisible by codility | Code Says
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.
Assume that the following declarations are given:
struct Results {
int * C;
int L;
};
Write a function:
struct Results solution(int A[], int N);
that, given a non-empty zero-indexed array A consisting of N integers, returns a sequence of integers representing the amount of non-divisors.
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:
http://www.martinkysel.com/codility-countnondivisible-solution/
- N is an integer within the range [1..50,000];
- each element of array A is an integer within the range [1..2 * N].
Using the Sieve of Eratosthenes, you generate divisors for all input elements of A. If a given number x is a divisor of element (x*N == element), then N also is a divisor. (N = element//x). After all divisors are computed, we simply subtract those (multiplied by their counts or 0) from the total number of elements in A.
def solution(A): A_max = max(A) count = {} for element in A: if element not in count: count[element] = 1 else: count[element] += 1 divisors = {} for element in A: divisors[element] = set([1, element]) # start the Sieve of Eratosthenes divisor = 2 while divisor*divisor <= A_max: element_candidate = divisor while element_candidate <= A_max: if element_candidate in divisors and not divisor in divisors[element_candidate]: divisors[element_candidate].add(divisor) divisors[element_candidate].add(element_candidate//divisor) element_candidate += divisor divisor += 1 result = [0] * len(A) for idx, element in enumerate(A): result[idx] = (len(A)-sum([count.get(divisor,0) for divisor in divisors[element]])) return result
1.首先定义一个vector counts来记录A中每个元素出现的次数
2.对任意一个i，计算A中A[i]的因子数。由于我们只需要计算小于或等于sqrt(A[i])的因子便可得出A[i]的所有因子，故外层循环：i，0~N-1
内层循环：j，1~sqrt(A[i])。若A[i] % j = 0则 j 是A[i]的因子，A[i]的因子数+1，若 j 不等于sqrt(A[i])，则A[i] / j 也是A[i]的因子，A[i]的因子数继续
+1。
3.最后，对每个i，res[i]等于N减去A[i]的因子数。
http://www.bubuko.com/infodetail-514634.htmlvector<int> solution(vector<int> &A) {// write your code in C++11int N = A.size();vector<int>::iterator max = max_element(A.begin(),A.end());vector<int> counts(*max+1,0);for(int i = 0 ; i < N ; ++i){counts[A[i]]++;}vector<int> res(N,0);for(int i = 0 ; i < N ; ++i){int divisors = 0;for(int j = 1 ; j*j <= A[i] ; ++j){if(A[i] % j == 0){divisors += counts[j];if(A[i]/j != j){divisors += counts[A[i]/j];}}}res[i] = N - divisors;}return res;}
我们可以用2 * N的空间统计数组A中每个数出现多少次。我们在用一张表tab[1..2 * N]，tab[i]记录数组A中出现的i的非约数有几个。起初我们认为tab[i] = N，即A中所有的数都不是i的约数。然后对于每个A中出现的数，类似筛法，我们求它所有的倍数j,从tab[j]中减掉i在A中出现的次数，因为i是j的约数。时间复杂度主要在筛法那里 是O(2Nlog(2N)) = O(NlogN)。空间复杂度主要是两张表，一张统计数在A出现多少次，一张是tab，因为数据范围是2 * N，所以这个空间还是O(N)的。
vector<int> solution(vector<int> &A) {
int n = A.size(), m = (n << 1) | 1;
vector<int> num;
num.resize(m + 1, 0);
for (int i = 0; i < n; ++i) {
++num[A[i]];
}
vector<int> answer;
answer.resize(m + 1, n);
for (int i = 1; i <= m; ++i) {
if (num[i]) {
for (int j = i; j <= m; j += i) {
answer[j] -= num[i];
}
}
}
vector<int> r;
for (int i = 0; i < n; ++i) {
r.push_back(answer[A[i]]);
}
return r;
}
http://codility-lessons.blogspot.com/2015/03/lesson-9-countnondivisible.htmlThe simplest solution is to check the occurrences of each value first, and then when we we given a number A[i], we check the divisors of A[i], which will be between 1 and sqrt(A[i]). We count the total number of the occurrences of all the divisors (and the answers for (A[i] / divisor) ) and and subtract it from N.
This solution gives the 100% score.
However, the time complexity of the part to check a number between 1 and sqrt(A[i]) is O(sqrt(N)) , so this is indeed O(N * sqrt(N)), while the problem requires a O(N * log(N) ) solution.
The O(N * sqrt(N)) solution
struct Results solution(int A[], int N)
{
//the number that may appear will be [1 ... 2 * N].
int size = sizeof(int) * (N * 2 + 1);
int* occurrence = (int*)alloca(size);
memset(occurrence, 0x00, size);
//allocate the memory for the result.
struct Results result;
result.C = (int*)calloc(N, sizeof(int));
result.L = N;
//now we check the array A and count the occurance for each number.
int i,j;
for (i = 0; i < N; i++){
occurrence[A[i]]++;
}
//now we compute the answer.
for (i = 0; i < N; i++){
int num = A[i];
int div_cnt = 0;
//count the number of the divisor while doing factorization.
for (j = 1; j * j < num; j++){
if (num % j == 0){
div_cnt += occurrence[j];
div_cnt += occurrence[num / j];
}
};
if (j * j == num){
div_cnt += occurrence[j];
}
result.C[i] = N - div_cnt;
}
return result;
}
The O(N * log(N)) solution
struct Results solution(int A[], int N)
{
//the number that may appear will be [1 ... 2 * N].
int size = sizeof(int) * (N * 2 + 1);
int* occurrence = (int*)alloca(size);
memset(occurrence, 0x00, size);
//the space to hold the answer for each value from 1 ... 2 * N.
//for now we initialize it
int* answer = (int*)alloca(size);
memset(answer, 0x00, size);
//allocate the memory for the result.
struct Results result;
result.C = (int*)calloc(N, sizeof(int));
result.L = N;
//now we check the array A and count the occurance for each number.
int i;
for (i = 0; i < N; i++){
occurrence[A[i]]++;
}
//now we compute the answer.
for (i = 1; i <= N * 2; i++){
int num = occurrence[i];
//the number doesn't in the array A, we can neglect it.
if (num == 0){
continue;
}
//if it appears in the array A,
//subtract its counts from cells at itss multiples in the answer array.
int j;
for (j = i; j <= N * 2; j += i){
answer[j] -= num;
}
}
//as the answer array contains the offset to N,
//N + answer[A[i]] will give the answer for each.
for (i = 0; i < N; i++){
result.C[i] = N + answer[A[i]];
}
return result;
}
http://codesays.com/2014/solution-to-count-non-divisible-by-codility/
Read full article from Solution to Count-Non-Divisible by codility | Code Says
