У меня есть вопрос относительно проблемы CountDiv в Codility.
Задача: написать функцию:
class Solution { public int solution(int A, int B, int K); }
что, учитывая три целых числа A, B и K, возвращает число целых чисел в пределах диапазона [A..B], которые делятся на K, то есть:
{ i : A ≤ i ≤ B, i mod K = 0 }
Мой код:
class Solution {
public int solution(int A, int B, int K) {
int start=0;
if (B<A || K==0 || K>B )
return 0;
else if (K<A)
start = K * ( A/K +1);
else if (K<=B)
start = K;
return (B-start+1)/K+ 1;
}
}
Я не понимаю, почему я ошибаюсь, особенно в этом случае:
extreme_ifempty
A = 10, B = 10, K in {5,7,20}
WRONG ANSWER
got 1 expected 0
if K =5, затем с i=10 A<=i<=B и i%k =0, так зачем мне 0? Описание проблемы.
Это решение 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 делится на любое положительное число, нам нужно его посчитать.
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;
}
Способ решения этой проблемы - с помощью Префикса Суммы, поскольку это является частью этого раздела в 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
}
}
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
Это мое решение 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);
}
}
Ключевые аспекты этого решения:
Вот мое простое решение со 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;
}
Если я правильно понял вопрос, я считаю, что это решение:
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 происходит из-за незаконной операции (деление на ноль)
Я не уверен, что вы пытаетесь сделать в своем коде, но более простым способом было бы использовать 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;
}
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;
}
Другое решение 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;
}
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;
}
}
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).
Здесь мое решение, две строки кода 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, вы должны добавить его в ответ.
Вот мое решение и получил 100%
public int solution(int A, int B, int K) {
int count = B/K - A/K;
if(A%K == 0) {
count++;
}
return count;
}
Я думаю, что ответы выше не дают достаточного логического объяснения, почему каждое решение работает (математика, лежащая в основе решения), поэтому я публикую свое решение здесь.
Идея состоит в том, чтобы использовать здесь арифметическую последовательность. Если у нас есть первое делимое число (> = 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% баллом
Столкнулся с проблемой и не смог найти решение, в котором использовалась техника 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) сложностью.
Это мое решение 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, вы должны добавить его в ответ.
Это решение 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();
}
Есть много отличных ответов, но я думаю, что в этом есть какая-то элегантность, а также 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 используется для деления чисел и пропуска оставшихся десятичных частей.
Я покажу свой код в го :)
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%
Если кто-то все еще заинтересован в этом упражнении, я поделюсь своим решением 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)
Однострочное решение Python 3 со счетом 100%
from math import ceil, floor
def solution(A, B, K):
return floor(B / K) - ceil(A / K) + 1
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;
}
Допущения: 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;