在范围内查找一个数字的倍数数量

Question

在范围内查找一个数字的倍数数量

16

关于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 = 10、A<=i<=B 和 i%k = 0，那么为什么我应该得到 0 呢？问题陈述。

- drevlav

嗯，我相信他们的意思是K等于5或7或20？ - Pham Trung

你能否发布问题的原始源代码吗？这个语句真的让我很困惑。 - nevets

27个回答

16

Java解决方案具有O(1)和100％的Codility，为那些想尝试而不是查看其他解决方案的人添加了一些测试用例和解决方案：

  // 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;
}

- moxi

1

JavaScript解决方案：

function solution(a, b, k) {
    return parseInt(b/k) - parseInt(a/k) + (a % k ? 0 : 1);
}

- the-catalin

不错，我记得曾经在推特上玩过解决方案，你的是一个很好的例子。 - moxi

10

解决这个问题的方法是使用前缀和，因为这是Codility中该部分的一部分。

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

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

使用这种技术，可以从0到A之间可被K整除的整数计数（A/K+1）中减去0到B之间可被K整除的整数计数（B/K+1）。

请记住，A是包含在内的，因此如果它是可被K整除的，则将其包括在结果中。

以下是我的解决方案：

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

- cheshy

1

嘿，我的朋友，+1 似乎对 a 和 b 都没有任何作用，因为它们互相抵消了。至少在 JavaScript 中，我会这样做：let a = Math.floor(A/K) ; let b = Math.floor(B/K).....所以，在 Java 中，你只需要使用 B/K 和 A/K 就可以了。

public int solution(int A, int B, int K) {
        int b = B/K; 
        int a = A/K; 

        if (A%K == 0) {
            --a;       
        }
        return b-a;     
    }

- Juan

这是因为C#和JavaScript处理类型和除法的方式不同。在上面的C#示例中，这是一个整数除法示例。JS没有整数，而是使用数字。 - whiteshooz

7

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

嗯，这是一行完全无法读懂的代码，但我发表它只是因为我可以;-)

完整的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

- HelpVampire666

解释得很好，但不是100%正确。准确度为75%。 - grzegorz_p

3

Python中的简单解决方案：

def solution(A, B, K):
    count = 0
    if A % K == 0:
        count += 1
    count += int((B / K) - int(A / K))
    return count

解释：

B/K is the total numbers divisible by K [1..B]

A/K is the total numbers divisible by K [1..A]

The subtracts gives the total numbers divisible by K [A..B]

if A%K == 0, then we need to add it as well.

- none

3

我认为上面的回答没有提供足够逻辑解释每个解决方案为什么可以工作(解决方案背后的数学知识)，因此我在这里发布我的解决方案。

这个想法是使用算术序列。如果我们有第一个可被整除的数字(>= A)和最后一个可被整除的数字(<= B)，我们就有了一个距离为K的算术序列。现在，我们所要做的就是找到范围[newA,newB]中总共有多少个能被范围[newA,newB]内的整数整除的项。

first term (a1) = newA
last/n-th term (an) = newB
distance (d) = K
Sn = a1 + (a1+K) + (a1 + 2k) + (a1 + 3k) + ... + (a1 + (n-1)K)

`n` in the above equation is what we are interested in finding. We know that

n-th term = an = a1 + (n-1)K 
as an = newB, a1 = newA so
newB = newA + (n-1)K
newB = newA + nK - K
nK = newB - newA + K
n = (newB - newA + K) / K

现在我们已经有了上述公式，只需要将其应用于代码中。

fun countDiv(A: Int, B: Int, K: Int): Int {
    //NOTE: each divisible number has to be in range [A, B] and we can not exceed this range
    //find the first divisible (by k) number after A (greater than A but less than B to stay in range)
    var newA = A
    while (newA % K != 0 && newA < B)
        newA++

    //find the first divisible (by k) number before B (less than B but greater than A to stay in range)
    var newB = B
    while (newB % K != 0 && newB > newA)
        newB--

    //now that we have final new range ([newA, newB]), verify that both newA and newB are not equal
    //because in that case there can be only number (newA or newB as both are equal) and we can just check
    //if that number is divisible or not
    if (newA == newB) {
        return (newA % K == 0).toInt()
    }

    //Now that both newA and newB are divisible by K (a complete arithmetic sequence)
    //we can calculate total divisions by using arithmetic sequence with following params
    //a1 = newA, an = newB, d = K
    // we know that n-th term (an) can also be calculated using following formula
    //an = a1 + (n - 1)d
    //n (total terms in sequence with distance d=K) is what we are interested in finding, put all values
    //newB = newA + (n - 1)K
    //re-arrange -> n =  (newB - newA + K) / K
    //Note: convert calculation to Long to avoid integer overflow otherwise result will be incorrect
    val result = ((newB - newA + K.toLong()) / K.toDouble()).toInt()
    return result
}

希望这能对某些人有所帮助。FYI，codility的解决方案得分100%

- Ramiz Raja

2

这是我的完美解决方案: 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);
    }
}

这个解决方案的关键点：

如果A等于1，那么约数的数量可以在B/K中找到。
如果A等于0，那么约数的数量可以在B/K加1中找到。
如果B等于0，则只有一个i%K=0，即零本身。

- Caesar Avgvstvs

如果你愿意尝试的话（至少在这种语言下），我不确定你是否能使其更加复杂。 - boatcoder

2

这是我的简单解决方案，100% 的正确率，最初的回答

public int solution(int A, int B, int K) {

    while (A % K != 0) {
        ++A;
    }
    while (B % K != 0) {
        --B;
    }
    return (B - A) / K + 1;
}

- Amrit Malla

通过将后置递增/递减更改为前置递增/递减，可以提高性能和内存使用率！ - PowerStat

没错，@PowerStat，它也可以通过另一种逻辑进行改进，如 B = (B/K)*K & int a = (A/K)*K 和 a==A?A=a:A+=K。 - Amrit Malla

2

这个可以使用O(1) 测试链接。

    using System;
    class Solution 
    {
      public int solution(int A, int B, int K) 
      {
       int value = (B/K)-(A/K);
       if(A%K == 0)
       {
        value=value+1;
       }
       return value;
      }
    }

- Buwaneka Kandekumbura

2

Python 3一行代码解决方案，得分100%

from math import ceil, floor


def solution(A, B, K):
    return floor(B / K) - ceil(A / K) + 1

- Haris Np

这应该是被接受的答案。这是运行时间复杂度为O(1)的最快解决方案。然而，为什么我们需要在末尾添加1呢？ - incarnate

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pham Trung · Accepted Answer

这是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可被任何正数整除，我们需要将其计入。