Найдите число делителей для числа в диапазоне

Ответ 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] которое делится на K равно X/K Таким образом, в диапазоне [A.. B], результат будет B/K - (A - 1)/K

В случае, когда A равно 0, так как 0 делится на любое положительное число, нам нужно его посчитать.

Ответ 2

Java-решение с O (1) и 100% в кодовости, добавив несколько тестовых примеров с решениями для тех, кто хочет попробовать и не видит других решений:

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

Ответ 3

Способ решения этой проблемы - с помощью Префикса Суммы, поскольку это является частью этого раздела в Codility.

https://codility.com/programmers/lessons/3/

https://codility.com/media/train/3-PrefixSums.pdf

Используя эту технику, можно вычесть количество целых чисел между 0 и A, которые делятся на K (A/K + 1) из числа целых чисел между 0 и B, которые делятся на K (B/K + 1).

Помните, что A является включающим, поэтому, если оно делится, включите его как часть результата.

Ниже мое решение:

class Solution {
public int solution(int A, int B, int K) {
        int b = (B/K) + 1;  // From 0 to B the integers divisible by K
        int a = (A/K) + 1;  // From 0 to A the integers divisible by K

        if (A%K == 0) { // "A" is inclusive; if divisible by K then
            --a;        //   remove 1 from "a"
        }
        return b-a;     // return integers in range
    }
}

Ответ 4

return A==B  ? (A%K==0 ? 1:0) : 1+((B-A)/K)*K /K; 

Ну, это совершенно неразборчивый oneliner, но я отправил его только потому, что могу: -)

полный код Java здесь:

package countDiv;

public class Solution {

    /**
     * First observe that
     * <li> the amount of numbers n in [A..B] that are divisible by K  is the same as the amount of numbers n between [0..B-A]
     *      they are not the same numbes of course, but the question is a range question.
     *      Now because we have as a starting point the zero, it saves a lot of code.
     * <li> For that matter, also A=-1000 and B=-100 would work
     * 
     * <li> Next, consider the corner cases.
     *      The case where A==B is a special one: 
     *      there is just one number inside and it either is divisible by K or not, so return a 1 or a 0. 
     * <li> if K==1 then the result is all the numbers between and including the borders.          
     * <p/>
     * So the algorithm simplifies to
     * <pre>
     * int D = B-A; //11-5=6
     * if(D==0) return B%K==0 ? 1:0;
     * int last = (D/K)*K; //6
     * int parts = last/K; //3
     * return 1+parts;//+1 because the left part (the 0) is always divisible by any K>=1.
     * </pre>
     * 
     * @param A : A>=1
     * @param B : 1<=A<=B<=2000000000
     * @param K : K>=1  
     */
    private static int countDiv(int A, int B, int K) {      
        return A==B  ? A%K==0 ? 1:0 : 1+((B-A)/K)*K /K; 
    }   

    public static void main(String[] args) {
        {
            int a=10;  int b=10; int k=5; int result=1;
            System.out.println( a + "..." + b + "/" + k + " = " +  countDiv(a,b,k)  + (result!=countDiv(a,b,k) ? " WRONG" :" (OK)" ));
        }

        {
            int a=10;  int b=10; int k=7; int result=0;
            System.out.println( a + "..." + b + "/" + k + " = " +  countDiv(a,b,k)  + (result!=countDiv(a,b,k) ? " WRONG" :" (OK)" ));
        }

        {
            int a=6;  int b=11; int k=2; int result=3;
            System.out.println( a + "..." + b + "/" + k + " = " +  countDiv(a,b,k)  + (result!=countDiv(a,b,k) ? " WRONG" :" (OK)" ));
        }

        {
            int a=6;  int b=2000000000; int k=1; int result=b-a+1;
            System.out.println( a + "..." + b + "/" + k + " = " +  countDiv(a,b,k)  + (result!=countDiv(a,b,k) ? " WRONG" :" (OK)" ));
        }
    }
}//~countDiv

Ответ 5

Это мое решение 100/100:

https://codility.com/demo/results/trainingRQDSFJ-CMR/

class Solution {
    public int solution(int A, int B, int K) {
        return (B==0) ? 1 : B/K + ( (A==0) ? 1 : (-1)*(A-1)/K);
    }
}

Ключевые аспекты этого решения:

• Если A = 1, то число делителей найдено в B/K.
• Если A = 0, то число делителей найдено в B/K плюс 1.
• Если B = 0, то существует только один i% K = 0, т.е. нуль.

Ответ 6

Вот мое простое решение со 100% https://app.codility.com/demo/results/trainingQ5XMG7-8UY/

public int solution(int A, int B, int K) {

    while (A % K != 0) {
        ++A;
    }
    while (B % K != 0) {
        --B;
    }
    return (B - A) / K + 1;
}

Ответ 7

Если я правильно понял вопрос, я считаю, что это решение:

public static int solution(int A, int B, int K) {
    int count = 0;
    if(K == 0) {
        return (-1);
    }
    if(K > B) {
        return 0;
    }
    for(int i = A; i <= B; ++i) {
        if((i % K) == 0) {
            ++count;
        }
    }
    return count;
}

возврат -1 происходит из-за незаконной операции (деление на ноль)

Ответ 8

Я не уверен, что вы пытаетесь сделать в своем коде, но более простым способом было бы использовать modulo operator (%).

public int solution(int A, int B, int K) 
{
    int noOfDivisors = 0;
    if(B < A || K == 0 || K > B )
        return 0;
    for(int i = A; i <= B; i++) 
    {
        if((i % K) == 0) 
        {
            noOfDivisors++;
        }
    }
    return noOfDivisors;
}

Ответ 9

int solution(int A, int B, int K) {
    int tmp=(A%K==0?1:0);
    int x1=A/K-tmp ;
    int x2=B/K;
    return x2-x1;
}

Ответ 10

Другое решение O (1), которое получило 100% в тесте.

int solution(int A, int B, int K) {
    if (A%K)   
        A = A+ (K-A%K);

    if (A>B)
        return 0;

    return (B-A)/K+1;
}

Ответ 11

100/100 - еще одна вариация решения, основанная на идее Pham Trung

class Solution {
    public int solution(int A, int B, int K) {
         int numOfDivs = A > 0 ? (B / K - ((A - 1) / K)) : ((B / K) + 1);
         return numOfDivs;
    }
}

Ответ 12

class Solution {
    public int solution(int A, int B, int K) {
        int a = A/K, b = B/K;
        if (A/K == 0)
            b++;
        return b - a;
    }
}

Это проходит test.

Он похож на "сколько чисел от 2 до 5". Мы все это знаем (5 - 2 + 1). Причина, по которой мы добавляем 1 в конце, состоит в том, что первое число 2 считается.

После A/K, B/K эта проблема становится той же, что и выше. Здесь нам нужно решить, имеет ли значение A в этой задаче. Только если A%K == 0, он подсчитывает, тогда нам нужно добавить 1 к результату b - a (то же самое с b+1).

Ответ 13

Здесь мое решение, две строки кода Java.

public int solution(int A, int B, int K) {
    int a = (A == 0) ? -1 : (A - 1) / K;
    return B / K - a;
}

Мысль проста.
а относится к числу чисел, делящихся в [1..A-1]
B/K означает, сколько чисел делится на [1..B]
0 делится на любое целое число, поэтому, если A равно 0, вы должны добавить его в ответ.

Ответ 14

Вот мое решение и получил 100%

public int solution(int A, int B, int K) {
    int count = B/K - A/K;
    if(A%K == 0) {
        count++;
    }
    return count;
}

• B/K даст вам общее число, делящееся на K [1..B]
• A/K даст вам общее число, делящееся на K [1..A]
• то вычтите, это даст вам общее число, делящееся на K [A..B]
• проверить A% K == 0, если true, то + 1 в count

Ответ 15

Я думаю, что ответы выше не дают достаточного логического объяснения, почему каждое решение работает (математика, лежащая в основе решения), поэтому я публикую свое решение здесь.

Идея состоит в том, чтобы использовать здесь арифметическую последовательность. Если у нас есть первое делимое число (> = A) и последнее делимое число (<= B), у нас есть арифметическая последовательность с расстоянием K. Теперь все, что нам нужно сделать, - это найти общее количество членов в диапазоне [newA, newB] которые являются общими делимыми числами в диапазоне [newA, newB]

first term (a1) = newA
last/n-th term (an) = newB
distance (d) = K
Sn = a1 + (a1+K) + (a1 + 2k) + (a1 + 3k) + ... + (a1 + (n-1)K)

'n' in the above equation is what we are interested in finding. We know that

n-th term = an = a1 + (n-1)K 
as an = newB, a1 = newA so
newB = newA + (n-1)K
newB = newA + nK - K
nK = newB - newA + K
n = (newB - newA + K) / K

Теперь, когда у нас есть формула выше, просто примените ее в коде.

fun countDiv(A: Int, B: Int, K: Int): Int {
    //NOTE: each divisible number has to be in range [A, B] and we can not exceed this range
    //find the first divisible (by k) number after A (greater than A but less than B to stay in range)
    var newA = A
    while (newA % K != 0 && newA < B)
        newA++

    //find the first divisible (by k) number before B (less than B but greater than A to stay in range)
    var newB = B
    while (newB % K != 0 && newB > newA)
        newB--

    //now that we have final new range ([newA, newB]), verify that both newA and newB are not equal
    //because in that case there can be only number (newA or newB as both are equal) and we can just check
    //if that number is divisible or not
    if (newA == newB) {
        return (newA % K == 0).toInt()
    }

    //Now that both newA and newB are divisible by K (a complete arithmetic sequence)
    //we can calculate total divisions by using arithmetic sequence with following params
    //a1 = newA, an = newB, d = K
    // we know that n-th term (an) can also be calculated using following formula
    //an = a1 + (n - 1)d
    //n (total terms in sequence with distance d=K) is what we are interested in finding, put all values
    //newB = newA + (n - 1)K
    //re-arrange -> n =  (newB - newA + K) / K
    //Note: convert calculation to Long to avoid integer overflow otherwise result will be incorrect
    val result = ((newB - newA + K.toLong()) / K.toDouble()).toInt()
    return result
}

Я надеюсь, что это помогает кому-то. К вашему сведению, кодовое решение со 100% баллом

Ответ 16

Столкнулся с проблемой и не смог найти решение, в котором использовалась техника Prefix Sum, которую я хочу. Вот мое решение:

Вопрос: Из A → B сколько чисел делится на K?

Ответ: prefSum [B + 1] - prefSum [A]

Пусть A, B, K 0,3,2; соответствующие значения prefSum равны [0,1,1,2,2] - с

prefSum [0] = 0

а также

prefSum [N] = (N-1)/K + 1;

Помните, что 0 делится на любое число. Вот код:

func Solution(A int, B int, K int) int {
    b := getPrefSum(B+1, K)
    a := getPrefSum(A, K)
    return b - a
}
func getPrefSum(N int, K int) int {
    if N == 0 {
        return 0
    }
    return (N-1)/K + 1
}

Он передается с O (1) сложностью.

Ответ 17

Это мое решение 100/100:

public int solution1(int A, int B, int K) {
    return A == 0 ? B / K - A / K + 1 : (B) / K - (A - 1) / K;
}

0 делится на любое целое число, поэтому, если A равно 0, вы должны добавить его в ответ.

Ответ 18

Это решение O (1), (нет необходимости в проверке для делимости a)

public static int countDiv(int a, int b, int k) {
        double l1 = (double)a / k;
        double l = -1 * Math.floor(-1 * l1);        
        double h1 = (double) b / k; 
        double h =  Math.floor(h1);
        Double diff = h-l+1;
        return diff.intValue();
    }

Ответ 19

Есть много отличных ответов, но я думаю, что в этом есть какая-то элегантность, а также 100% -ная экономичность.

public int solution(int a, int b, int k) {
    return Math.floorDiv(b, k) - Math.floorDiv(a-1, k);
}

Объяснение: Число целых чисел в диапазоне [1.. B] которые делятся на K равно B/K Диапазон [A.. B] может быть преобразован в [1.. B] - [1.. A) (обратите внимание, что круглая скобка после A означает, что A не принадлежит этому диапазону). Это дает в результате B/K - (A-1)/K Math.floorDiv используется для деления чисел и пропуска оставшихся десятичных частей.

Ответ 20

Я покажу свой код в го :)

func CountDiv(a int, b int, k int) int {
   count := int(math.Floor(float64(b/k)) - math.Floor(float64(a/k)));
   if (math.Mod(float64(a), float64(k)) == 0) {
      count++
   }

   return count
}

Общая оценка 100%

Ответ 21

Если кто-то все еще заинтересован в этом упражнении, я поделюсь своим решением Python (100% в Codility)

def solution(A, B, K):

    if not (B-A)%K:
        res = int((B-A)/K)
    else:
        res = int(B/K) - int(A/K)

    return res + (not A%K)

Ответ 22

Однострочное решение Python 3 со счетом 100%

from math import ceil, floor


def solution(A, B, K):
    return floor(B / K) - ceil(A / K) + 1

Ответ 23

int solution(int A, int B, int K)
{
    // write your code in C++14 (g++ 6.2.0)
    int counter = 0;

    if (A == B)
        A % K == 0 ? counter++ : 0;
    else
    {
        counter = (B - A) / K;

        if (A % K == 0) counter++;
        else if (B % K == 0) counter++;
        else if ((counter*K + K) > A && (counter*K + K) < B) counter++;
    }

    return counter;
}

Ответ 24

Допущения: A и B - целые числа в диапазоне [0..2,000,000,000]; K представляет собой целое число в диапазоне [1..2.000.000.000]; A ≤ B.

int from = A+(K-A%K)%K;
if (from > B) {
    return 0;
}
return (B-from)/K + 1;