查找範圍內的數字的因數

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(); 
    }