java - 什么测试用例可以打破这个包含/排除原则挑战的解决方案？

Question

我正在应对一项编程挑战，其中一个问题涉及包含/排除原则问题，我认为我已经解决了这个问题，但在一些测试用例中一直失败。我想不出它们可能是什么(2 个测试用例失败，但它们没有显示输出)。你能给我一些关于它们可能是什么的想法吗？

原问题:

K caterpillars are eating their way through N leaves, each caterpillar falls from leaf to leaf in a unique sequence, all caterpillars start at a twig at position 0 and falls onto the leaves at position between 1 and N. Each caterpillar j has as associated jump number Aj. A caterpillar with jump number j eats leaves at positions that are multiple of j. It will proceed in the order j, 2j, 3j…. till it reaches the end of the leaves and it stops and build its cocoon. Given a set A of K elements K<-15, N<=10^9, we need to determine the number of uneaten leaves.

Input:

N = No of uneaten leaves K = No. of caterpillars A = Array of integer jump numbers

Output:

The integer nu. Of uneaten leaves

Sample Input:

10 3 2 4 5

Output:

4

Explanation:

[2, 4, 5] is a j member jump numbers, all leaves which are multiple of 2, 4, and 5 are eaten, leaves 1,3,7,9 are left, and thus the no. 4

我的解决方案:

static int countUneatenLeaves(int N, int[] A) {
    int total = 0;
    for (int i = 0; i < A.length; i++) {
        int multiplier = (int) Math.pow(-1, i);
        total += multiplier * combination(A, i + 1, N);
    }
    return N - total;
}

public static int combination(int[] elements, int K, int num) {

    // get the length of the array
    // e.g. for {'A','B','C','D'} => N = 4 
    int N = elements.length;

    // get the combination by index 
    // e.g. 01 --> AB , 23 --> CD
    int combination[] = new int[K];

    // position of current index
    //  if (r = 1)              r*
    //  index ==>       0   |   1   |   2
    //  element ==>     A   |   B   |   C
    int r = 0;
    int index = 0;
    int total = 0;
    while (r >= 0) {
        // possible indexes for 1st position "r=0" are "0,1,2" --> "A,B,C"
        // possible indexes for 2nd position "r=1" are "1,2,3" --> "B,C,D"

        // for r = 0 ==> index < (4+ (0 - 2)) = 2
        if (index <= (N + (r - K))) {
            combination[r] = index;

            // if we are at the last position print and increase the index
            if (r == K - 1) {

                //do something with the combination e.g. add to list or print
                total += calc(combination, elements, num);
                index++;
            } else {
                // select index for next position
                index = combination[r] + 1;
                r++;
            }
        } else {
            r--;
            if (r > 0) index = combination[r] + 1;
            else index = combination[0] + 1;
        }
    }
    return total;
}

private static int calc(int[] combination, int[] elements, int num) {

    int eaten = 0;
    if (combination.length == 1) {
        eaten = (int) Math.floor(num / elements[combination[0]]);
    } else {
        int lcm = lcm(elements[combination[0]], elements[combination[1]]);
        for (int i = 2; i < combination.length; i++) {
            lcm = lcm(lcm, elements[combination[i]]);
        }
        eaten = Math.abs((int) Math.floor(num / lcm));
    }
    return eaten;
}

private static int lcm(int a, int b) {
    return a * (b / findGCD(a, b));
}

private static int findGCD(int number1, int number2) {
    //base case
    if (number2 == 0) {
        return number1;
    }

    return findGCD(number2, number1 % number2);
}

我自己尝试了很多测试输入，但未能找到它中断的情况。我怀疑失败的测试涉及大 N，就好像我采用简单的蛮力方法一样，相同的测试用例因超时而失败。

有什么想法吗？

Answer 1

我认为您应该使用 long to 而不是 int。因为A的元素可以更接近10^9。所以当 num gcd(a, b) 较小时，比如 1，lcm(a, b) = a * b 可能大于 0x7FFFFFFF，所以答案不正确。