algorithm - How to find the number of values in a given range divisible by a given value?

Question

I have three numbers x, y , z.

For a range between numbers x and y.

How can i find the total numbers whose % with z is 0 i.e. how many numbers between x and y are divisible by z ?

Answer 1

它可以在 O(1) 中完成：找到第一个，找到最后一个，找到所有其他的计数。

我假设范围是包容性的。如果您的范围是独占的，请将边界调整一：

• 找到x能被 整除的第一个值z。您可以丢弃x：

  x_mod = x % z;
  
  if(x_mod != 0)
    x += (z - x_mod);
  

• y找到能被 整除的最后一个值y。您可以丢弃y：

  y -= y % z;
  

• 找到这个范围的大小：

  if(x > y)
    return 0;
  else
    return (y - x) / z + 1;
  

如果数学floor和ceil函数可用，前两部分可以写得更易读。最后一部分也可以使用数学函数进行压缩：

 x = ceil  (x, z);
 y = floor (y, z);
 return max((y - x) / z + 1, 0);

如果保证输入是有效范围 ( x >= y)，则最后一个测试 或max是不必要的：

 x = ceil  (x, z);
 y = floor (y, z);
 return (y - x) / z + 1;

Answer 2

^{（2017年，由于评论而重写了答案）}数字n中z
的倍数很简单n / z

/作为整数除法，意味着可能由除法产生的小数被简单地忽略（例如17/5 => 3而不是3.4）。

现在，在从x到y的范围内，有多少个z的倍数？

让我们看看我们有多少个m到y

0----------------------------------x------------------------y
-m---m---m---m---m---m---m---m---m---m---m---m---m---m---m---

你知道我要去哪里......得到范围内的倍数[ x, y ]，得到y的倍数然后减去x之前的倍数，(x-1) / z

解决方案：( y / z ) - (( x - 1 ) / z )

---

以编程方式，您可以创建一个函数numberOfMultiples

function numberOfMultiples(n, z) {
   return n / z;
}

获取范围内的倍数[x, y]

numberOfMultiples(y) - numberOfMultiples(x-1)

该函数是O(1)，不需要循环来获取倍数。

您应该找到的结果示例

• [30, 90] ÷ 13 => 4
• [1, 1000] ÷ 6 => 166
• [100, 1000000] ÷ 7 => 142843
• [777, 777777777] ÷ 7 => 111111001

对于第一个示例，90 / 13 = 6、(30-1) / 13 = 2和6-2 = 4

---26---39---52---65---78---91--
     ^                      ^
     30<---(4 multiples)-->90

Answer 3

我也在 Codility 上遇到过这个问题。我花了比我想承认的时间更长的时间来提出一个好的解决方案，所以我想我会分享我认为是一个优雅的解决方案！

直截了当的方法 1/2：

带有循环和计数器的 O(N) 时间解决方案，当 N = 20 亿时不现实。

很棒的方法3：

我们想要某个范围内可被 K 整除的位数。

简单情况：假设范围 [0 .. n*K], N = n*K

N/K 表示 [0,N) 中可被 K 整除的位数，给定 N%K = 0（又名 N 可被 K 整除）

前任。N = 9，K = 3，数字位数 = |{0 3 6}| = 3 = 9/3

相似地，

N/K + 1 表示[0,N]中能被K整除的位数

前任。N = 9，K = 3，数字位数 = |{0 3 6 9}| = 4 = 9/3 + 1

我认为真正理解上述事实是这个问题中最棘手的部分，我无法准确解释它为什么起作用。其余的归结为前缀和处理特殊情况。

---

现在我们并不总是有一个以 0 开头的范围，而且我们不能假设这两个边界可以被 K 整除。但是等等！我们可以通过计算我们自己的上界和下界并使用一些减法魔法来解决这个问题:)

1. 首先找到范围 [A,B] 中能被 K 整除的最接近的上限和下限。

   • 上限（更容易）：例如。B = 10, K = 3, new_B = 9... 模式是 B - B%K
   • 下限：例如。A = 10, K = 3, new_A = 12...多试几次，你会看到模式是 A - A%K + K

2. 然后使用上述技术计算以下内容：

   • 确定 [0,B] 之间可被 K 整除的数字 X 的总数
   • 确定 [0,A) 之间可被 K 整除的 Y 的总位数

3. 通过表达式 X - Y 在常数时间内计算 [A,B] 之间可被 K 整除的位数

网站：https ://codility.com/demo/take-sample-test/count_div/

class CountDiv {
    public int solution(int A, int B, int K) {
        int firstDivisible = A%K == 0 ? A : A + (K - A%K);
        int lastDivisible = B%K == 0 ? B : B - B%K; //B/K behaves this way by default.
        return (lastDivisible - firstDivisible)/K + 1;
    }
}

这是我第一次解释这样的方法。非常感谢您的反馈:)

Answer 4

这是 Codility 第 3 课的问题之一。对于这个问题，输入保证在有效范围内。我使用Javascript回答了它：

function solution(x, y, z) {
    var totalDivisibles =  Math.floor(y / z),
        excludeDivisibles = Math.floor((x - 1) / z),
        divisiblesInArray = totalDivisibles - excludeDivisibles;
   return divisiblesInArray;
}

https://codility.com/demo/results/demoQX3MJC-8AP/

（我实际上想询问此页面上的其他一些评论，但我还没有足够的代表点）。

Answer 5

除以y-x，z四舍五入。添加一个 ify%z < x%z或 if x%z == 0。

没有数学证明，除非有人愿意在 Perl 中提供一个测试用例：

#!perl
use strict;
use warnings;
use Test::More;

sub multiples_in_range {
  my ($x, $y, $z) = @_;
  return 0 if $x > $y;
  my $ret = int( ($y - $x) / $z);
  $ret++ if $y%$z < $x%$z or $x%$z == 0;
  return $ret;
}   

for my $z (2 .. 10) {
  for my $x (0 .. 2*$z) {
    for my $y (0 .. 4*$z) {
      is multiples_in_range($x, $y, $z),
         scalar(grep { $_ % $z == 0 } $x..$y),
         "[$x..$y] mod $z";
    }
  }
}

done_testing;

输出：

$ prove divrange.pl 
divrange.pl .. ok      
All tests successful.
Files=1, Tests=3405,  0 wallclock secs ( 0.20 usr  0.02 sys +  0.26 cusr  0.01 csys =  0.49 CPU)
Result: PASS

Answer 6

设[A;B]为包含A和B的正整数区间，使得0 <= A <= B, K为除数。

不难看出区间有KN(A) = ⌊A / K⌋ = floor(A / K)的因子：[0;A]

         1K       2K       3K       4K       5K
●········x········x··●·····x········x········x···>
0                    A

同理，区间中有KN(B) = ⌊B / K⌋ = floor(B / K)的因数：[0;B]

         1K       2K       3K       4K       5K
●········x········x········x········x···●····x···>
0                                       B

然后N = N(B) - N(A)等于 range 中K的数量（可被K整除的整数的数量）(A;B]。点A不包括在内，因为减去的N(A)部分包括该点。A mod K因此，如果为零，则结果应加一：

N := N(B) - N(A)

if (A mod K = 0)
  N := N + 1

PHP中的实现

function solution($A, $B, $K) {
  if ($K < 1)
    return 0;

  $c = floor($B / $K) - floor($A / $K);

  if ($A % $K == 0)
    $c++;

  return (int)$c;
}

在PHP中，floor函数的效果可以通过强制转换为整数类型来实现：

$c = (int)($B / $K) - (int)($A / $K);

我认为哪个更快。

Answer 7

这是我在 C++ 中的简短而简单的解决方案，它在代码性上得到了 100/100。:) 在 O(1) 时间内运行。我希望它不难理解。

int solution(int A, int B, int K) {
    // write your code in C++11
    int cnt=0;
    if( A%K==0 or B%K==0)
        cnt++;
    if(A>=K)
        cnt+= (B - A)/K;
    else
        cnt+=B/K;

    return cnt;
}

Answer 8

(floor)(high/d) - (floor)(low/d) - (high%d==0)

解释：

从 0.0 到 a 有可被 d 整除的 a/d 数。(d!=0)

因此 (floor)(high/d) - (floor)(low/d) 将给出在 (low,high] 范围内可整除的数字（注意，不包括低，高包括在此范围内）

现在要从范围中删除高点，只需减去 (high%d==0)

适用于整数、浮点数或其他任何东西（对浮点数使用 fmodf 函数）

Answer 9

不会争取 o(1) 解决方案，这留给更聪明的人:) 只是觉得这是函数编程的完美使用场景。简单明了。

 > x,y,z=1,1000,6
 => [1, 1000, 6] 
 > (x..y).select {|n| n%z==0}.size
 => 166 

编辑：在阅读了其他人的 O(1) 解决方案之后。我觉得很丢脸。编程让人懒得思考……

Answer 10

解决方案的时间复杂度将是线性的。

代码片段：

int countDiv(int a, int b, int m)
{
    int mod = (min(a, b)%m==0);
    int cnt  = abs(floor(b/m) - floor(a/m))  +  mod;
    return cnt;
}

Answer 11

根据定义划分 (a/b=c) - 采用一组大小为 a 并形成大小为 b 的组。可以形成的这种大小的组的数量 c 是 a 和 b 的商。- 只不过是范围/区间]0..a]（不包括零，但包括a）内可被b整除的整数个数。

所以根据定义：
Y/Z - ]0..Y] 内可被 Z 整除的整数个数
和
X/Z - ]0..X] 内可被 Z 整除的整数个数

因此：
结果 = [Y/Z] - [X/Z] + x（其中 x = 1 当且仅当 X 可被 Y 整除，否则为 0 - 假设给定范围 [X..Y] 包括 X）

例如：
对于 (6, 12, 2) 我们有 12/2 - 6/2 + 1 (as 6%2 == 0) = 6 - 3 + 1 = 4 // {6, 8, 10, 12
} (5, 12, 2) 我们有 12/2 - 5/2 + 0 (as 5%2 != 0) = 6 - 2 + 0 = 4 // {6, 8, 10, 12}

Answer 12

这里 n 将为您提供数字计数，并将打印所有可被整除的数字的总和k

int a = sc.nextInt();
int b = sc.nextInt();
int k = sc.nextInt();
int first = 0;

if (a > k) {
  first = a + a/k;
} else {
  first = k;
}

int last = b - b%k;

if (first > last) {
  System.out.println(0);
} else {
  int n = (last - first)/k+1;
  System.out.println(n * (first + last)/2);
}

Answer 13

这是用Swift Programming Language编写的问题的解决方案。

第 1 步：找到可被 z 整除的范围内的第一个数字。

第 2 步：找到可被 z 整除的范围内的最后一个数字。

第 3 步：使用数学公式找出该范围内能被 z 整除的数。

func solution(_ x : Int, _ y : Int, _ z : Int) -> Int {
    var numberOfDivisible = 0

    var firstNumber: Int
    var lastNumber: Int

    if y == x {
        return x % z == 0 ? 1 : 0
    }
    
    //Find first number divisible by z
    let moduloX = x % z

    if moduloX == 0 {
        firstNumber = x
    } else {
        firstNumber = x + (z - moduloX)
    }

    //Fist last number divisible by z
    let moduloY = y % z
    if moduloY == 0 {
        lastNumber = y
    } else {
        lastNumber = y - moduloY
    }

    //Math formula
    numberOfDivisible = Int(floor(Double((lastNumber - firstNumber) / z))) + 1

    return numberOfDivisible
}

Answer 14

公共静态int解决方案（int A，int B，int K）{

        int count = 0;

        //If A is divisible by K
        if(A % K == 0)
        {
            count = (B / K) - (A / K) + 1;
        }
        //If A is not divisible by K
        else if(A % K != 0)
        {
            count = (B / K) - (A / K);
        }

        return count;

}