找到范围内数字的除数

Question

我对Codility中的CountDiv问题有疑问.

给出的问题是:写一个函数:

class Solution { public int solution(int A, int B, int K); }

给定三个整数A,B和K,返回可被K整除的[A..B]范围内的整数,即:

{ i : A ? i ? B, i mod K = 0 }

我的代码:

class Solution {
    public int solution(int A, int B, int K) {        
         int start=0;
         if (B<A || K==0 || K>B )
            return 0;
         else if (K<A)
            start = K * ( A/K +1);
         else if (K<=B)
            start = K;

         return (B-start+1)/K+ 1;
    }
} 

我不明白为什么我错了,特别是这个测试用例:

extreme_ifempty 
A = 10, B = 10, K in {5,7,20}
WRONG ANSWER 
got 1 expected 0

如果K =5再与i=10 A<=i<=B和i%k =0,所以我为什么应该有0？问题陈述.

Answer 1

这是O(1)解决方案,通过了测试

int solution(int A, int B, int K) {
    int b = B/K;
    int a = (A > 0 ? (A - 1)/K: 0);
    if(A == 0){
        b++;
    }
    return b - a;
}

说明:在范围的整数数[1 .. X]是整除K的X/K.因此,在该范围内[A .. B],结果是B/K - (A - 1)/K

如果A为0,因为0可以被任何正数整除,我们需要计算它.

Answer 2

具有O(1)和100%可编程性的Java解决方案,为那些想要尝试但没有看到其他解决方案的人添加一些测试用例和解决方案:

  // Test cases
  //  [1,1,1] = 1
  // [0,99,2] = 50
  // [0, 100, 3] = 34  
  // [11,345,17] = 20
  // [10,10,5] = 1
  // [3, 6, 2] = 2
  // [6,11,2] = 3  
  // [16,29,7] = 2
  // [1,2,1] = 2    
public int solution(int A, int B, int K) {
   int offsetForLeftRange = 0;
   if ( A % K == 0) { ++offsetForLeftRange; }

   return  (B/K) - (A /K) + offsetForLeftRange;
}

Answer 3

解决这个问题的方法是Prefix Sums,因为这是Codility中该部分的一部分.

https://codility.com/programmers/lessons/3/

https://codility.com/media/train/3-PrefixSums.pdf

使用这种技术,可以从0和B之间的整数计数中减去0和A之间可被K(A/K + 1)整除的整数计数,这些整数可被K(B/K + 1)整除.

请记住,A是包容性的,因此如果它是可分的,那么将其作为结果的一部分包括在内.

以下是我的解决方案:

class Solution {
public int solution(int A, int B, int K) {
        int b = (B/K) + 1;  // From 0 to B the integers divisible by K
        int a = (A/K) + 1;  // From 0 to A the integers divisible by K

        if (A%K == 0) { // "A" is inclusive; if divisible by K then
            --a;        //   remove 1 from "a"
        }
        return b-a;     // return integers in range
    }
}

Answer 4

return A==B  ? (A%K==0 ? 1:0) : 1+((B-A)/K)*K /K; 

嗯,这是一个完全难以辨认的oneliner但我发布它只是因为我可以;-)

这里完整的java代码:

package countDiv;

public class Solution {

    /**
     * First observe that
     * <li> the amount of numbers n in [A..B] that are divisible by K  is the same as the amount of numbers n between [0..B-A]
     *      they are not the same numbes of course, but the question is a range question.
     *      Now because we have as a starting point the zero, it saves a lot of code.
     * <li> For that matter, also A=-1000 and B=-100 would work
     * 
     * <li> Next, consider the corner cases.
     *      The case where A==B is a special one: 
     *      there is just one number inside and it either is divisible by K or not, so return a 1 or a 0. 
     * <li> if K==1 then the result is all the numbers between and including the borders.          
     * <p/>
     * So the algorithm simplifies to
     * <pre>
     * int D = B-A; //11-5=6
     * if(D==0) return B%K==0 ? 1:0;
     * int last = (D/K)*K; //6
     * int parts = last/K; //3
     * return 1+parts;//+1 because the left part (the 0) is always divisible by any K>=1.
     * </pre>
     * 
     * @param A : A>=1
     * @param B : 1<=A<=B<=2000000000
     * @param K : K>=1  
     */
    private static int countDiv(int A, int B, int K) {      
        return A==B  ? A%K==0 ? 1:0 : 1+((B-A)/K)*K /K; 
    }   

    public static void main(String[] args) {
        {
            int a=10;  int b=10; int k=5; int result=1;
            System.out.println( a + "..." + b + "/" + k + " = " +  countDiv(a,b,k)  + (result!=countDiv(a,b,k) ? " WRONG" :" (OK)" ));
        }

        {
            int a=10;  int b=10; int k=7; int result=0;
            System.out.println( a + "..." + b + "/" + k + " = " +  countDiv(a,b,k)  + (result!=countDiv(a,b,k) ? " WRONG" :" (OK)" ));
        }

        {
            int a=6;  int b=11; int k=2; int result=3;
            System.out.println( a + "..." + b + "/" + k + " = " +  countDiv(a,b,k)  + (result!=countDiv(a,b,k) ? " WRONG" :" (OK)" ));
        }

        {
            int a=6;  int b=2000000000; int k=1; int result=b-a+1;
            System.out.println( a + "..." + b + "/" + k + " = " +  countDiv(a,b,k)  + (result!=countDiv(a,b,k) ? " WRONG" :" (OK)" ));
        }
    }
}//~countDiv

Answer 5

如果我正确理解了这个问题，我相信这就是解决方案：

public static int solution(int A, int B, int K) {
    int count = 0;
    if(K == 0) {
        return (-1);
    }
    if(K > B) {
        return 0;
    }
    for(int i = A; i <= B; ++i) {
        if((i % K) == 0) {
            ++count;
        }
    }
    return count;
}

返回 -1 是由于非法操作（除以零）