Как найти количество значений в заданном диапазоне, делящихся на заданное значение?

Ответ 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;

Ответ 2

^{(2017, ответ переписан благодаря комментариям)}
Число кратных z в числе n просто 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

Ответ 3

Я также столкнулся с этим на Codility. Мне потребовалось гораздо больше времени, чем мне хотелось бы признаться, чтобы придумать хорошее решение, поэтому я решил, что поделюсь тем, что я считаю элегантным решением!

Прямой подход 1/2:

O (N) временное решение с циклом и счетчиком, нереально, когда N = 2 млрд.

Удивительный подход 3:

Нам нужно количество цифр в некотором диапазоне, которые делятся на K.

Простой случай: предположим, диапазон [0.. n * K], N = n * K

N/K представляет количество цифр в [0, N), которые делятся на K, учитывая, что N% K = 0 (иначе, N делится на K)

ех. N = 9, K = 3, Num цифр = | {0 3 6} | = 3 = 9/3

Аналогичным образом,

N/K + 1 представляет количество цифр в [0, N], делимое на K

ех. N = 9, K = 3, Num цифр = | {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. Затем рассчитайте следующее, используя вышеописанную технику:

   • Определите общее количество цифр X между [0, B], которые делятся на K
   • Определите общее количество цифр Y между [0, A), которые делятся на K

3. Рассчитайте количество цифр между [A, B], которые делятся на K в постоянное время по выражению X - Y

Веб-сайт: 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;
    }
}

Я впервые объясняю такой подход. Обратная связь очень ценится :)

Ответ 4

Это один из вопросов урока Codility Lesson 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/

(Я действительно хотел спросить о некоторых других комментариях на этой странице, но пока у меня недостаточно очков повторения).

Ответ 5

Разделите y-x на z, округляя вниз. Добавьте один, если y%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

Ответ 6

Вот мое короткое и простое решение на С++, которое получило 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;
}

Ответ 7

Пусть [A;B] - интервал положительных целых чисел, включающий A и B, что 0 <= A <= B, K - дивизор.

Нетрудно видеть, что в интервале [0;A] существуют N(A) = ⌊A / K⌋ = floor(A / K) факторы K:

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

Аналогично, существуют N(B) = ⌊B / K⌋ = floor(B / K) факторы K в интервале [0;B]:

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

Тогда N = N(B) - N(A) равно числу 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);

который, я думаю, быстрее.

Ответ 8

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

Объяснение:

Существуют числа a/d, делящиеся на d от 0.0 до a. (Д!= 0)

Следовательно, (пол) (высокий/д) - (пол) (низкий/д) даст числа, делящиеся в диапазоне (низкий, высокий) (обратите внимание, что низкий исключается, и высокий уровень включен в этот диапазон)

Теперь, чтобы удалить верхний из диапазона, просто вычтите (высокий% d == 0)

Работает для целых чисел, поплавков и т.д. (используйте функцию fmodf для поплавков)

Ответ 9

Не будет стремиться к решению o (1), это уйдет для более умного человека:) Просто чувствуйте, что это идеальный сценарий использования для программирования функций. Простой и понятный.

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

EDIT: после чтения другого решения O (1). Мне стыдно. Программирование заставило людей лениться думать...

Ответ 10

Разделение (a/b = c) по определению - взятие набора размеров a и формирование групп размера b. Число групп такого размера, которое может быть сформировано, c, является частным от a и b. - это не более чем число целых чисел в пределах диапазона/интервала] 0..a] (не считая нуля, но включая a), которые делятся на b.

поэтому по определению:
Y/Z - число целых чисел внутри] 0..Y], которые делятся на Z и
X/Z - число целых чисел внутри] 0..X], которые делятся на Z

следующим образом:
result = [Y/Z] - [X/Z] + x (где x = 1 тогда и только тогда, когда X делится на Y в противном случае 0 - если данный диапазон [X..Y] включает X)

пример:
для (6, 12, 2) имеем 12/2 - 6/2 + 1 (как 6% 2 == 0) = 6 - 3 + 1 = 4//{6, 8, 10, 12}
для (5, 12, 2) имеем 12/2 - 5/2 + 0 (как 5% 2!= 0) = 6 - 2 + 0 = 4//{6, 8, 10, 12}

Ответ 11

Временная сложность решения будет линейной.

Фрагмент кода:

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

Ответ 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);
}