查找范围内数字的倍数

algorithm java

2022-09-03 08:21:22

我有一个关于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

如果然后与，那么为什么我应该有0？问题陈述。K =5i=10A<=i<=Bi%k =0

答案 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]KX/K[A .. B]B/K - (A - 1)/K

如果 A 为 0，由于 0 可被任何正数整除，因此我们需要将其计数。

答案 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;
}