Java CountNonDivisible - Codility 训练任务

CountNonDivisible - Codility training task

提问by stepler

I'm traning on codility now. Some tasks I can solve by myself, but with some tasks have problems. Difficulty of this task is <**>. It's medium, but I stalled.

我现在正在训练 codility。有些任务我可以自己解决，但有些任务有问题。这个任务的难度是<**>。它是中等的，但我停了下来。

Problem:

问题：

---

---

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:

给定一个由 N 个整数组成的非空零索引数组 A。对于每个满足 0 ≤ i < N 的数字 A[i]，我们要计算数组中不是 A[i] 的除数的元素的数量。我们说这些元素是非因数。例如，考虑整数 N = 5 和数组 A，使得：

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:

写一个函数：

class Solution { public int[] solution(int[] A); }

that, given a non-empty zero-indexed array A consisting of N integers, returns a sequence of integers representing the numbers of non-divisors. The sequence should be returned as:

给定一个由 N 个整数组成的非空零索引数组 A，返回一个整数序列，表示非除数的个数。该序列应返回为：

• 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).

• 一个结构结果（在 C 中），
• 或整数向量（在 C++ 中），
• 或记录结果（Pascal），
• 或整数数组（使用任何其他编程语言）。

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:

如上所述，该函数应返回 [2, 4, 3, 2, 0]。假使，假设：

• N is an integer within the range [1..50,000];
• each element of array A is an integer within the range [1..2 * N].

• N 是 [1..50,000] 范围内的整数；
• 数组 A 的每个元素都是 [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).

• 预期的最坏情况时间复杂度为 O(N*log(N))；
• 预期的最坏情况空间复杂度为 O(N)，超出输入存储（不包括输入参数所需的存储）。

Elements of input arrays can be modified.

可以修改输入数组的元素。

---

---

I have written some solutions. But my solutions bulky and still have O(n^2) complexity. Can you help me with some ideas or algorithms how to do it optimally? It's not an interview task or something else. I'm just training and try to solve all tasks. You can find this task here: http://codility.com/demo/train/Lesson 9, first task in lesson.

我已经写了一些解决方案。但是我的解决方案笨重并且仍然具有 O(n^2) 复杂性。你能帮我提供一些想法或算法如何以最佳方式做到这一点吗？这不是面试任务或其他什么。我只是在训练并尝试解决所有任务。您可以在此处找到此任务：http: //codility.com/demo/train/第 9 课，课程中的第一个任务。

Thank you!

谢谢！

采纳答案by Marco13

A solution attempt: (EDITED, see below)

解决方案尝试：（已编辑，见下文）

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 static void main(String[] args)
    {
        int A[] = new int[5];
        A[0] = 3;
        A[1] = 1;
        A[2] = 2;
        A[3] = 3;
        A[4] = 6;

        Solution s = new Solution();
        int B[] = s.solution(A);
        System.out.println("Input  : "+Arrays.toString(A));
        System.out.println("Result : "+Arrays.toString(B));
    }

    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 <= maxValue; i++)
        {
            int next = i + i;
            while (next <= maxValue)
            {
                divisors.get(next).addAll(divisors.get(i));
                prime.set(next, Boolean.FALSE);
                next += i;
            }
        }
        return divisors;
    }

    /**
     * Computes an array of length 2*A.length+1, 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 + 1];
        for (int i=0; i<A.length; i++)
        {
            int value = A[i];
            occurances[value]++;
        }
        return occurances;
    }
}

The maximum value for the numbers that occur in the array was defined to be 2*arrayLength. For each number that MAY occur in the array, it computes

数组中出现的数字的最大值定义为 2*arrayLength。对于数组中可能出现的每个数字，它计算

• The set of divisors of this number (using the Erathostenes Sieve)
• How often the number actually occurs in the array

• 该数字的除数集（使用 Erathostenes Sieve）
• 该数字在数组中实际出现的频率

Given this information, one can walk through the array. For each value that is found in the array, one can look up the set of divisors, and compute the total number occurences of all the divisors. The result is then simply the array length, minus this total number of occurances of divisors.

有了这些信息，就可以遍历整个数组。对于在数组中找到的每个值，可以查找除数集，并计算所有除数出现的总数。结果就是数组长度减去除数出现的总数。

Since it uses only the Sieve of Erathostenes for the computation (and only walks through the set of divisors for each number, which should be logN as well), it should have a worst-case time complexity of O(N*logN). But I'm not entirely sure whether the storage complexity really can be considered to be strictly O(N), because for each of the N numbers, it has to store the set of divisors. Maybe this can somehow be avoided, by combining some of the methods, but in any case, the storage is at least in O(N*logN) as well.

由于它仅使用 Erathostenes 筛法进行计算（并且只遍历每个数字的除数集，也应该是 logN），因此它应该具有 O(N*logN) 的最坏情况时间复杂度。但我不完全确定存储复杂度是否真的可以被认为是严格的 O(N)，因为对于 N 个数字中的每一个，它都必须存储一组除数。也许这可以通过组合一些方法以某种方式避免，但无论如何，存储至少也是 O(N*logN) 。

EDIT: The exceptions came from the array for the occurrences storing only values up to A.length*2-1, this was fixed now. Additionally, the set of divisors was not computed properly, this should also be fixed now. Apart from that, analysis results like

编辑：异常来自数组，用于仅存储高达 A.length*2-1 的值，现在已修复。此外，除数集没有正确计算，现在也应该修复。除此之外，分析结果如

got      [8, 8, 9, 10, 6, 8, .. 
expected [8, 8, 9, 10, 6, 8, ..

are not really helpful. Maybe this is part of the "game", but I'm not playing this game right now. The basic idea should be clear, and I assume that it's now working properly until someone shows be a counterexample ;-P It still does not reach the O(N) storage complexity, but I haven't thought about a possible way to achieve this thoroughly...

不是很有帮助。也许这是“游戏”的一部分，但我现在不玩这个游戏。基本思路应该很清楚了，我假设它现在可以正常工作，直到有人证明是反例；-P 它仍然没有达到 O(N) 存储复杂度，但我还没有想过实现这一点的可能方法彻底...

回答by Felipe Barbosa

To understand why number "2" appears twice on following result [2,4,3,2,0] see code below

要了解为什么数字“2”在以下结果 [2,4,3,2,0] 中出现两次，请参阅下面的代码

A[0] = 3, the non-divisors are: 2, 6       >> Quantity: 2
A[1] = 1, the non-divisors are: 3, 2, 3, 6 >> Quantity: 4
A[2] = 2, the non-divisors are: 3, 3, 6,   >> Quantity: 3
A[3] = 3, the non-divisors are: 2, 6       >> Quantity: 2
A[6] = 6, there aren't any non-divisors.   >> Quantity: 0

回答by user3157761

Because that return numbers represents the quantity of non-divisors! For index [0] there are 2 non-divisers and for index [3] there are 2 non-divisers also.

因为那个返回数字代表非除数的数量！对于索引 [0]，有 2 个非除数，对于索引 [3]，也有 2 个非除数。

回答by furqan

/**
 * Count Non-divisible
 */

public class Solution {

    public int[] solution(int[] A) {
        int[] div = new int[A.length];
        for (int e = 0; e < div.length; e++) {
            div[e] = 0;
            for (int i = 0; i < A.length; i++) {
                int dividend = A[e];
                if (dividend % A[i] != 0) {
                    div[e] += 1;
                }
            }
        }
        return div;
    }

    public static void main(String args[]) {
        int[] A = new int[]{3, 1, 2, 3, 6};
        Solution s = new Solution();
        int[] B = s.solution(A);
        for (int i = 0; i < B.length; i++) {
            System.out.println(B[i]);
        }
    }
}

回答by stepler

This solution gives 100 score. https://codility.com/demo/results/demo63KVRG-Q63/

该解决方案给出 100 分。https://codility.com/demo/results/demo63KVRG-Q63/

public int[] solution(int[] A) {
    int[][] D = new int[A.length*2 + 1][2];

    for (int i = 0; i < A.length; i++) {
        D[A[i]][0]++;
        D[A[i]][1] = -1;
    }

    for (int i = 0; i < A.length; i++) {
        if (D[A[i]][1] == -1) {
            D[A[i]][1] = 0;
            for (int j = 1; j <= Math.sqrt(A[i]) ; j++) {
                if (A[i] % j == 0 && A[i] / j != j) {
                    D[A[i]][1] += D[j][0];
                    D[A[i]][1] += D[A[i]/j][0];
                } else if (A[i] % j == 0 && A[i] / j == j) {
                    D[A[i]][1] += D[j][0];
                }
            }
        }
    }
    for (int i = 0; i < A.length; i++) {
        A[i] = A.length - D[A[i]][1];
    }
    return A;
}

Thank you all for your help.

谢谢大家的帮助。

回答by Sheng

Here is my 100 score Python solution. Hope it is helpful to others.

这是我的 100 分 Python 解决方案。希望对其他人有帮助。

def solution(A):
    ''' Solution for the CountNonDivisible by codility
        Author: Sheng Yu - codesays.com
    '''
    from math import sqrt

    A_max = max(A)
    A_len = len(A)

    # Compute the frequency of occurrence of each
    # element in array A
    count = {}
    for element in A:
        count[element] = count.get(element,0)+1

    # Compute the divisors for each element in A
    divisors = {}
    for element in A:
        # Every nature number has a divisor 1.
        divisors[element] = [1]
    # In this for loop, we only find out all the
    # divisors less than sqrt(A_max), with brute
    # force method.
    for divisor in xrange(2, int(sqrt(A_max))+1):
        multiple = divisor
        while multiple  <= A_max:
            if multiple in divisors and not divisor in divisors[multiple]:
                divisors[multiple].append(divisor)
            multiple += divisor
    # In this loop, we compute all the divisors
    # greater than sqrt(A_max), filter out some
    # useless ones, and combine them.
    for element in divisors:
        temp = [element/div for div in divisors[element]]
        # Filter out the duplicate divisors
        temp = [item for item in temp if item not in divisors[element]]
        divisors[element].extend(temp)

    # The result of each number should be, the array length minus
    # the total number of occurances of its divisors.
    result = []
    for element in A:
        result.append(A_len-sum([count.get(div,0) for div in divisors[element]]))

    return result

回答by jaho

I thought I'll share my solution in C++ which gets 100 score. I think it's pretty straightforward.

我想我会在 C++ 中分享我的解决方案，得到 100 分。我认为这很简单。

https://codility.com/demo/results/demoQFK5R5-YGD/

https://codility.com/demo/results/demoQFK5R5-YGD/

1. First it counts the occurrences of each number in the array.

2. Then for each array element iit finds the number of its divisors in a range from 1 to sqrt(i), including the divisors which are the result of the division.

3. Finally it subtracts a total number of divisors for given element from a total number of elements in the array.

   vector<int> solution(vector<int> &A) {
   
       int N = A.size();
       vector<int> counts (*std::max_element(A.begin(), A.end()) + 1,0);
   
       // Calculate occurences of each number in the array
       for (int i = 0; i < N; ++i)
       {
           counts[A[i]] += 1;
       }
   
       std::vector<int> answer(N,0);
   
       // For each element of the array
       for (int i = 0; i < N; ++i)
       {
           // Calulate how many of its divisors are in the array
           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];
                   }
               }
           }
   
           // Subtract the number of divisors from the number of elements in the array
           answer[i] = N - divisors;
       }
   
       return answer;
   }
   

1. 首先它计算数组中每个数字的出现次数。

2. 然后对于每个数组元素i，它在 1 到 的范围内找到其除数的数量sqrt(i)，包括作为除法结果的除数。

3. 最后，它从数组中的元素总数中减去给定元素的除数总数。

   vector<int> solution(vector<int> &A) {
   
       int N = A.size();
       vector<int> counts (*std::max_element(A.begin(), A.end()) + 1,0);
   
       // Calculate occurences of each number in the array
       for (int i = 0; i < N; ++i)
       {
           counts[A[i]] += 1;
       }
   
       std::vector<int> answer(N,0);
   
       // For each element of the array
       for (int i = 0; i < N; ++i)
       {
           // Calulate how many of its divisors are in the array
           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];
                   }
               }
           }
   
           // Subtract the number of divisors from the number of elements in the array
           answer[i] = N - divisors;
       }
   
       return answer;
   }
   

回答by Roman

This worked for me with 100% score on C

这对我有用，在 C 上的得分为 100%

struct Results solution(int A[], int N) {
    struct Results result;
    // write your code in C99

    int *numbers = (int *)calloc(2*N + 1, sizeof(int));
    for (int i = 0; i < N; i++) {
        ++numbers[A[i]];
    }

    int *numbers2 = (int *)calloc(2*N + 1, sizeof(int));
    for (int i = 0; 2*i < 2*N + 1; i++) {
        if (numbers[i] != 0) {
            for (int j = 2*i; j < 2*N + 1; j+=i) {
                numbers2[j] += numbers[i];
            }
        }
    }


    int * Carr = (int *)calloc(N, sizeof(int));

    for (int i = 0; i < N; i++) {
        Carr[i] = N - numbers[A[i]] - numbers2[A[i]];
    }


    result.C = Carr;
    result.L = N;

    free(numbers);
    free(numbers2);
    return result;
}

回答by mcm

100% for Javascript. https://codility.com/demo/results/demoKRRRPF-8JW/

100% 为 Javascript。https://codility.com/demo/results/demoKRRRPF-8JW/

function solution(A) {
    var N = A.length;
    if (N < 1 || N > 50000) throw 'Error: Bad input';

    var uniqueDict = {};
    var keys = [];
    for (var i = 0; i < N; ++i) {
        var num = A[i]
        var uniqueCount = uniqueDict[num];
        if (uniqueCount > 0) {
            uniqueDict[num] = uniqueCount + 1;
        } else {
            uniqueDict[num] = 1;
            keys.push(num);
        }
    }

    keys.sort(function(a,b){
        return a-b;
    });

    for (i = keys.length-1; i >= 0; --i) {
        num = keys[i];
        var divisorCount = divisors(num, uniqueDict);

        var nonDivisorCount = N - divisorCount;
        uniqueDict[num] = nonDivisorCount;
    }

    for (i = 0; i < N; ++i) {
        num = A[i];
        A[i] = uniqueDict[num];
    }
    return A;
}

function divisors(num, uniqueDict) {
    var count = 0;
    var x = 1;
    while (x * x <= num) {
        if (parseInt(num/x) === num/x) { // is divisor
            if (uniqueDict[num/x] > 0) {
                count += uniqueDict[num/x];
            }
            if (num/x !== x && uniqueDict[x] > 0) {
                count += uniqueDict[x];
            }
        }
        x++;
    }
    return count;
}

回答by Shadi Al Barhouch

Here we go with the solution I got 100% on:

在这里，我们使用我 100% 的解决方案：

boolean[] result_;
public int[] solution(int[] A) {
int a[][] = new int[2*A.length +  1][2];
result_ = new boolean[2*A.length +  1];
for(int i : A) {
    ++a[i][0];
}
a[1][1] = A.length - a[1][0];
result_[1] = true;
for(int i : A) {
    multCount(a,A,i);
}
int[] result = new int[A.length];
for(int i=0;i<result.length; i++) {
    result[i] = a[A[i]][1];
}
return result;

}

private void multCount( int[][] a, int[] A, int item) {
if( result_[item] )
    return;
int sub=(int)Math.sqrt(item);
  a[item][1] = A.length;
if(item % sub == 0&& sub >1){

    a[item][1] -=  a[sub][0];
    int rest = item/sub;
    if(rest != sub) {

        a[item][1] -=  a[rest][0];
    }
}

 a[item][1] -= a[item][0];
 a[item][1] -= a[1][0];
for(int i=2; i<sub; i++) {
    if(item % i == 0) {
        a[item][1] -= a[i][0];

        int rest = item/i;

        a[item][1] -=  a[rest][0];

    }
}
result_[item] = true;
   }

https://codility.com/demo/results/trainingZ2VRTK-5Y9/

https://codility.com/demo/results/trainingZ2VRTK-5Y9/