algorithm - valor - tabla de divisibilidad

¿Cómo encontrar el número de valores en un rango dado divisible por un valor dado?

Question

Tengo tres números x, y, z.

Para un rango entre los números x y y.

¿Cómo puedo encontrar los números totales cuyo% con z es 0, es decir, cuántos números entre x e y son divisibles por z?

Answer 1

Aquí está mi solución corta y simple en C ++ que obtuvo 100/100 en codilidad. :) Se ejecuta en tiempo O (1). Espero que no sea difícil de entender.

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 2

Divide yx por z , redondeando hacia abajo. Agregue uno si y%z < x%z o si x%z == 0 .

Ninguna prueba matemática, a menos que alguien se preocupe por proporcionar una, pero los casos de prueba, 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;

Salida:

$ 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 3

División (a / b = c) por definición: toma un conjunto de tamaño a y forma grupos de tamaño b. El número de grupos de este tamaño que se pueden formar, c, es el cociente de a y b. - no es más que el número de enteros dentro del rango / intervalo] 0..a] (sin incluir cero, pero incluyendo a) que son divisibles por b.

así por definición:
Y / Z - número de enteros dentro de] 0..Y] que son divisibles por Z
y
X / Z - número de enteros dentro de] 0..X] que son divisibles por Z

así:
resultado = [Y / Z] - [X / Z] + x (donde x = 1 si y solo si X es divisible por Y de lo contrario 0 - asumiendo el rango dado [X..Y] incluye X)

ejemplo:
para (6, 12, 2) tenemos 12/2 - 6/2 + 1 (como 6% 2 == 0) = 6 - 3 + 1 = 4 // {6, 8, 10, 12}
para (5, 12, 2) tenemos 12/2 - 5/2 + 0 (como 5% 2! = 0) = 6 - 2 + 0 = 4 // {6, 8, 10, 12}

Answer 4

Esta es una de las preguntas de la Lección de Codilidad 3. Para esta pregunta, se garantiza que la entrada está en un rango válido. Lo respondí utilizando 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/

(De hecho, quería preguntar sobre algunos de los otros comentarios en esta página, pero aún no tengo suficientes puntos de repetición).

Answer 5

La complejidad temporal de la solución será lineal.

Fragmento de código :

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 6

No nos esforzaremos por una solución o (1), esto lo dejará para una persona más inteligente :) Simplemente piense que este es un escenario de uso perfecto para la programación de funciones. Sencillo y directo.

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

EDITAR: después de leer la solución O (1) de otros. Me siento avergonzado. La programación hizo que la gente fuera perezosa a pensar ...

Answer 7

Se puede hacer en O (1): encontrar el primero, encontrar el último, encontrar el recuento de todos los demás.

Supongo que el rango es inclusivo. Si sus rangos son exclusivos, ajuste los límites en uno:

• encuentra el primer valor después de x que es divisible por z . Puedes descartar x :

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

• encuentra el último valor antes de y que es divisible por y . Puedes descartar y :

  y -= y % z;

• Encuentra el tamaño de este rango:

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

Si las funciones matemáticas de floor y ceil están disponibles, las dos primeras partes se pueden escribir de manera más legible. También la última parte se puede comprimir usando funciones matemáticas:

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

Si se garantiza que la entrada es un rango válido ( x >= y ), la última prueba o el max es innecesario:

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

Answer 8

Sea [A;B] un intervalo de enteros positivos, incluidos A y B, de modo que 0 <= A <= B , K sea ​​el divisor.

Es fácil ver que hay N(A) = ⌊A / K⌋ = floor(A / K) factores de K en el intervalo [0;A] :

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

De forma similar, hay N(B) = ⌊B / K⌋ = floor(B / K) de K en el intervalo [0;B] :

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

Entonces N = N(B) - N(A) es igual al número de K ''s (el número de enteros divisibles por K ) en el rango (A;B] . El punto A no está incluido, porque la N(A) restada N(A) incluye este punto . Por lo tanto, el resultado debe incrementarse en uno, si A mod K es cero:

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

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

Implementación 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, el efecto de la función de floor se puede lograr mediante la conversión al tipo entero:

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

Lo cual, creo, es más rápido.

Answer 9

También me encontré con esto en Codility. Me tomó mucho más tiempo de lo que me gustaría admitir para encontrar una buena solución, ¡así que pensé que compartiría lo que creo que es una solución elegante!

Enfoque directo 1/2:

Solución de tiempo O (N) con un bucle y un contador, poco realista cuando N = 2 mil millones.

Enfoque impresionante 3:

Queremos el número de dígitos en algún rango que son divisibles por K.

Caso simple: asumir rango [0 .. n * K], N = n * K

N / K representa el número de dígitos en [0, N) que son divisibles por K, dado que N% K = 0 (alias. N es divisible por K)

ex. N = 9, K = 3, números numéricos = | {0 3 6} | = 3 = 9/3

Similar,

N / K + 1 representa el número de dígitos en [0, N] divisible por K

ex. N = 9, K = 3, números numéricos = | {0 3 6 9} | = 4 = 9/3 + 1

Creo que entender realmente el hecho anterior es la parte más difícil de esta pregunta, no puedo explicar exactamente por qué funciona. El resto se reduce a sumas de prefijo y manejo de casos especiales .

Ahora no siempre tenemos un rango que comience con 0, y no podemos asumir que los dos límites serán divisibles por K. ¡Pero espere! Podemos solucionar esto calculando nuestros propios límites superiores e inferiores y usando un poco de magia de sustracción :)

1. Primero, encuentre la parte superior e inferior más cercana en el rango [A, B] que son divisibles por K.

   • Límite superior (más fácil): ej. B = 10, K = 3, new_B = 9 ... el patrón es B - B% K
   • Límite inferior: ej. A = 10, K = 3, new_A = 12 ... intente unos cuantos más y verá que el patrón es A - A% K + K

2. Luego calcula lo siguiente usando la técnica anterior:

   • Determine el número total de dígitos X entre [0, B] que son divisibles por K
   • Determine el número total de dígitos Y entre [0, A) que son divisibles por K

3. Calcule el número de dígitos entre [A, B] que son divisibles por K en tiempo constante mediante la expresión X - Y

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

Esta es la primera vez que explico un enfoque como este. La retroalimentación es muy apreciada :)

Answer 10

^{( 2017, respuesta reescrita gracias a los comentarios )}
El número de múltiplos de z en un número n es simplemente n / z

Siendo la división entera, lo que significa que los decimales que podrían resultar de la división simplemente se ignoran (por ejemplo, 17/5 => 3 y no 3.4 ).

Ahora, en un rango de x a y , ¿cuántos múltiplos de z hay?

Veamos cuántos múltiplos m tenemos hasta y

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

Verá a dónde voy ... para obtener el número de múltiplos en el rango [ x, y ] , obtener el número de múltiplos de y luego restar el número de múltiplos antes de x , (x-1) / z

Solución: ( y / z ) - (( x - 1 ) / z )

Programáticamente, podrías hacer una función numberOfMultiples

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

para obtener el número de múltiplos en un rango [x, y]

numberOfMultiples(y) - numberOfMultiples(x-1)

La función es O (1) , no hay necesidad de un bucle para obtener el número de múltiplos.

Ejemplos de resultados que deberías encontrar.

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

Para el primer ejemplo, 90 / 13 = 6 , (30-1) / 13 = 2 , y 6-2 = 4

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

Answer 11

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

Explicación:

Hay números a / d divisibles por d de 0.0 a a. (d! = 0)

Por lo tanto, (piso) (alto / d) - (piso) (bajo / d) dará números divisibles en el rango (bajo, alto) (Tenga en cuenta que bajo se excluye y alto se incluye en este rango)

Ahora para eliminar alto del rango solo reste (alto% d == 0)

Trabajos para enteros, flotadores o lo que sea (use la función fmodf para flotadores)