Comment trouver le nombre de valeurs dans une plage donnée divisible par une valeur donnée?

Il peut être fait en O(1): trouver la première, trouver le dernier, de trouver le nombre de tous les autres.

Je suis en supposant que la plage est inclusive. Si vos gammes sont exclusifs, d'ajuster les limites par un:

• trouver la première valeur après x qui est divisible par z. Vous pouvez jeter x:

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

• trouver la dernière valeur avant y qui est divisible par y. Vous pouvez jeter y:

  y -= y % z;
  

• de trouver la taille de cette gamme:

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

Si mathématique floor et ceil fonctions sont disponibles, les deux premières parties peuvent plus être rédigé lisiblement. En outre, la dernière partie peut être compressé à l'aide de fonctions mathématiques:

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

si l'entrée est la garantie d'une plage valide (x >= y), le dernier test ou max est inutile:

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

J'ai aussi rencontré ce sur Codility. Il m'a fallu beaucoup plus de temps que je le voudrais à admettre pour arriver à une bonne solution, alors j'ai pensé que je voudrais partager ce que je pense est une solution élégante!

Approche Simple 1/2:

O(N) le temps de la solution avec une boucle et de contre, irréaliste quand N = 2 milliards de dollars.

Génial Approche 3:

Nous voulons que le nombre de chiffres dans une certaine gamme qui sont divisibles par K.

Cas Simple: supposons que l'intervalle [0 .. n*K], N = n*K

N/K représente le nombre de chiffres dans [0,N) qui sont divisibles par K, étant donné N%K = 0 (aka. N est divisible par K)

ex. N = 9, K = 3, Num chiffres = |{0 3 6}| = 3 = 9/3

De même,

N/K + 1 représente le nombre de chiffres dans [0,N] divisible par K

ex. N = 9, K = 3, Num chiffres = |{0 3 6 9}| = 4 = 9/3 + 1

Je pense vraiment à comprendre le fait ci-dessus est la partie la plus délicate de cette question, je ne peux pas expliquer exactement pourquoi il fonctionne.
Le reste se résume à préfixe sommes et de manutention des cas particuliers.

Maintenant, nous n'avons pas toujours une gamme qui commence par 0, et nous ne pouvons pas assumer les deux limites sera divisible par K.
Mais attendez! On peut résoudre ce problème par le calcul de notre belle limites supérieure et inférieure, et grâce à la soustraction de la magie 🙂

1. D'abord trouver le plus proche inférieure et supérieure de l'intervalle [A,B] qui sont divisibles par K.

   • Limite supérieure (plus facile): ex. B = 10, K = 3, new_B = 9... le motif est B - B%K
   • Limite inférieure: ex. A = 10, K = 3, new_A = 12... essayez un peu plus et vous verrez, le motif est Un - Un%K + K

2. Puis de calculer le suit, en utilisant la technique ci-dessus:

   • De déterminer le nombre total de chiffres X de [0,B] qui sont divisibles par K
   • De déterminer le nombre total de chiffres Y entre [0,A) qui sont divisibles par K

3. Calculer le nombre de chiffres entre [A,B] qui sont divisibles par K en temps constant par l'expression X - Y

Site web: 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;
    }
}

C'est ma première fois d'expliquer une telle approche. La rétroaction est très apprécié 🙂

Diviser y-x par z, arrondi vers le bas. Ajouter un si y%z < x%z ou si x%z == 0.

Pas une preuve mathématique, à moins que quelqu'un se soucie d'en fournir un, mais des cas de test, en 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;

De sortie:

$ 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

Laisser [A;B] avoir un intervalle d'entiers positifs dont Un et B tels que 0 <= A <= B, K être le diviseur.

Il est facile de voir qu'il y a N(A) = ⌊A /K⌋ = floor(A /K) facteurs de K dans l'intervalle [0;A]:

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

De même, il y a N(B) = ⌊B /K⌋ = floor(B /K) facteurs de K dans l'intervalle [0;B]:

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

Puis N = N(B) - N(A) est égal au nombre de K's (le nombre d'entiers divisibles par K) dans la gamme (A;B]. Le point Un n'est pas inclus, parce que le soustrait N(A) comprend ce point de. Par conséquent, le résultat doit être incrémenté, si A mod K est égale à zéro:

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

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

Implémentation en 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;
}

En PHP, l'effet de la floor fonction peut être réalisée par moulage de type integer:

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

qui, je pense, est plus rapide.

De ne pas viser un o(1) de la solution, ce congé pour plus personne intelligente:) Juste l'impression que c'est un parfait scénario d'utilisation de la fonction de programmation. Simple et directe.

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

EDIT: après lecture des autres O(1) solution. Je me sens humiliée. La programmation des gens paresseux pour penser...

Le temps de la complexité de la solution sera linéaire.

Extrait De Code :

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