查找范围内的数字的因数

Question

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

给出的问题是：写功能：

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

，鉴于三个整数A，B和K，返回在该范围[A..B]内的整数的数目整除K，即：

{ 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=10A<=i<=B和i%k =0所以我为什么要拥有0？ Problem statement。

Answer 1

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

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是由于非法操作（被零除）

Answer 2

我不知道你是什么试图在你的代码中做，但更简单的方法是使用模运算符（％）。

public int solution(int A, int B, int K) 
{ 
    int noOfDivisors = 0; 
    if(B < A || K == 0 || K > B) 
     return 0; 
    for(int i = A; i <= B; i++) 
    { 
     if((i % K) == 0) 
     { 
      noOfDivisors++; 
     } 
    } 
    return noOfDivisors; 
} 

Answer 3

这是O（1）溶液，将其通过test

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 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

int solution(int A, int B, int K) { 
    int tmp=(A%K==0?1:0); 
    int x1=A/K-tmp ; 
    int x2=B/K; 
    return x2-x1; 
} 

Answer 6

在测试中获得100％的另一个O（1）解决方案。

int solution(int A, int B, int K) { 
    if (A%K) 
     A = A+ (K-A%K); 

    if (A>B) 
     return 0; 

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

Answer 7

Java解决方案与O（1）和codility 100％，增加一些测试用例，对于那些谁想要尝试，而不是看别人解决方案：

// 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 8

100/100 - 其他该解决方案的变化，基于范忠的想法

class Solution { 
    public int solution(int A, int B, int K) { 
     int numOfDivs = A > 0 ? (B/K - ((A - 1)/K)) : ((B/K) + 1); 
     return numOfDivs; 
    } 
} 

Answer 9

class Solution { 
    public int solution(int A, int B, int K) { 
     int a = A/K, b = B/K; 
     if (A/K == 0) 
      b++; 
     return b - a; 
    } 
} 

这传递test。

它类似于“多少个数字从2到5”。我们都知道这是(5 - 2 + 1)。我们最后加上1的原因是第一个数字2是重要的。

A/K, B/K之后，这个问题与上面的问题相同。在这里，我们需要确定A是否在这个问题中。只有在A%K == 0的情况下，它才会计数，那么我们需要将1添加到结果b - a（与b+1相同）。

Answer 10

这是我的100/100溶液：该溶液的

https://codility.com/demo/results/trainingRQDSFJ-CMR/

class Solution { 
    public int solution(int A, int B, int K) { 
     return (B==0) ? 1 : B/K + ((A==0) ? 1 : (-1)*(A-1)/K); 
    } 
} 

关键方面：

1. 如果A = 1，则除数的数在B被发现/ K。
2. 如果A = 0，则在B/K加1中找到除数的数量。
3. 如果B = 0，则只有一个i％K = 0，即零本身。

Answer 11

解决此问题的方法是通过前缀和，因为这是Codility中该部分的一部分。

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

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

使用这种技术可以减去用K整除0和A之间的整数的计数（A/K + 1）从0和B之间的整数的计数可以被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 12

这里是我的解决方案，Java代码两行。

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

这个想法很简单。
a是指在[1..A-1]中有多少个数可以被整除
B/K是指有多少个数可以在[1 ..B]
0可以被整数整除，所以如果A是0，则应该在答案中加1。

Answer 13

int solution(int A, int B, int K) 
{ 
    // write your code in C++14 (g++ 6.2.0) 
    int counter = 0; 

    if (A == B) 
     A % K == 0 ? counter++ : 0; 
    else 
    { 
     counter = (B - A)/K; 

     if (A % K == 0) counter++; 
     else if (B % K == 0) counter++; 
     else if ((counter*K + K) > A && (counter*K + K) < B) counter++; 
    } 

    return counter; 
} 

Answer 14

这是我的100/100的解决方案：

public int solution1(int A, int B, int K) { 
    return A == 0 ? B/K - A/K + 1 : (B)/K - (A - 1)/K; 
} 

0是任意整数整除，所以如果A是0，你应该添加一个答案。

Answer 15

这里是我的解决方案，并获得100％

public int solution(int A, int B, int K) { 
    int count = B/K - A/K; 
    if(A%K == 0) { 
     count++; 
    } 
    return count; 
} 

1. 为b/K会给你的总数由K [1..B]
2. 一/ K会给你总整除可以被K整除的数字[1..A]
3. 然后减去，这会给你可以被K除尽的总数[A..B]
4. 检查A％K == 0，如果为真，则+ 1到计数

Answer 16

这是O（1）溶液中，（没有用于a的divisility需要检查）

public static int countDiv(int a, int b, int k) { 
     double l1 = (double)a/k; 
     double l = -1 * Math.floor(-1 * l1);   
     double h1 = (double) b/k; 
     double h = Math.floor(h1); 
     Double diff = h-l+1; 
     return diff.intValue(); 
    }