Оптимизировать код, чтобы получить количество целых чисел в заданном диапазоне, которые делятся на целое число
Дан диапазон х, у. Мне нужно посчитать все числа между ними и делятся на n.
Я знаю, простой способ сделать это, циклически по всему диапазону
for(int i=x;i<=y;i++) if(i%n ==0) counter++;
Счетчик содержит ответ.
Но это работает очень медленно для больших диапазонов. например, х =0, а у =3 000 000 000.
Я уверен, что есть какое-то отношение, которое я могу использовать, чтобы уменьшить количество итераций и оптимизировать этот код для скорости. Я искал, но я не мог найти это. Может ли кто-нибудь помочь мне с этим, пожалуйста.
Спасибо.
10 ответов
Это работает: (e+1 - s) / d + (e%d < (s+d-1)%d), (Он использует семантику C и целочисленную арифметику и предполагает, что начало неотрицательно. S - начальное значение, e - конечное значение [включительно], а d - делитель.)
Обновлено: лучшее решение e/d - (s-1)/d, Это было вдохновлено User448810. Это требует, чтобы быть позитивным; обработка нуля или отрицательного значения s (или e) требует корректировки усечения до нуля (для этой задачи мы бы хотели установить отрицательную бесконечность).
Обновление для отрицательных значений: Следующее работает для любых значений s и e в диапазоне их типов при условии, что s <= e и 0 По сути, первые два утверждения эквивалентны e = e < 0 ? (e+1)/d - 1 : e/d;
s = s <= 0 ? s/d - 1 : (s-1)/d;
return e-s;
e = e/d а также s = (s-1)/d с делением, измененным на округление к -infinity вместо нуля (так что -1/10 дает -1, а не 0).
(floor)(high/d) - (floor)(low/d) - (high%d==0)
Объяснение:
Есть числа a/d, которые делятся на d от 0 до a. (Д!=0)
Поэтому (floor)(high/d) - (floor)(low/d) даст числа, делимые на диапазон (низкий, высокий) (обратите внимание, что низкий исключен, а высокий включен в этот диапазон)
Теперь, чтобы убрать максимум из диапазона, просто вычтите (максимум%d==0)
Используйте fmodf для float.
Только эта реализация работает для меня (A, B в [0..2kkk]; K в [1..2kkk]):
function solution(A, B, K) {
if(B < K) return A === 0 ? 1 : 0;
if(A === B) return A % K === 0 ? 1 : 0;
var pre = A === 0 ? 2 : 1;
var min = A < K ? K : A + A % K;
var max = B - B % K;
return (max - min) / K + pre;
}
Я уверен, что вы можете сделать это:
public static int numDivisible(int low, int high, int test) {
return (high-low)/test;
}
Вот и ты. Решение с постоянным временем. Так как вам не нужно точно знать, какие числа делятся, вам не нужно перебирать их все.
РЕДАКТИРОВАТЬ: Измените это на следующее, как в @Chaser324.
public static float numDivisible(float low, float high, float test) {
return Math.ceil((high-low)/test);
}
РЕДАКТИРОВАТЬ: маленькая опечатка т.е. text в test
public int myfunc(int low, int high, int test) {
int count = 0;
if(low % test == 0)
count++;
count +=(high-low)/test;
return count;
}
Пожалуйста, предоставьте комментарии по алгоритму ниже: Предположим, диапазон составляет [R1,R2], а число, которое нужно разделить, равно n.
Найдите наименьшее число, начиная с R1, делимое на n. Назовите его маленьким.
Найти наибольшее число, начиная с R2, делимого на n. Назовите это большим.
Общее число, которое делится = (большое-маленькое)/n + 1.
Худший случай - все еще O(n), но мог бы быть эффективным для большой разницы между R1 и R2. Надеюсь, я рассмотрел все случаи. Пожалуйста, предложите.
int numofDivisible(int R1, int R2, int n) {
int small = R1, large= R2;
if ((R1 > R2) || (n==0)) return 0;
if (R1 == R2) {
if (R1 % n == 0)
return 1;
else
return 0;
}
while(small <= R2){
if(small % n == 0)
break;
++small;
}
if (small > R2)
return 0;
while (large > small) {
if (large % n == 0)
break;
--large;
}
if (large == small)
return 1;
return ((large-small)/n + 1);
}
Вы просили подсчитать количество целых чисел между x и y (оба x и y включены в диапазон), которые делятся на n. Нет необходимости в каком-либо цикле, и только два деления необходимы для вычисления ответа. Давайте рассмотрим простой пример: для целого числа от 100 до 200 сколько целых делится на 7?
Начните с нижнего предела диапазона: 100 / 7 = 14 с остатком 2. Теперь делитель 7 минус остаток 2 равен 5, поэтому наименьшее число в диапазоне, которое делится на 7, равно 100 + 5 = 105.
Теперь перейдите к верхнему пределу диапазона: 200 / 7 = 28 с остатком 4, поэтому наибольшее число в диапазоне, которое делится на 7, равно 200 - 4 = 196.
Таким образом, числа в диапазоне, которые делятся на 7, равны 105, 112, 119, 126, 133, 140, 147, 154, 161, 168, 175, 182, 189 и 196. Есть 14 из них, которые вы Можно рассчитать несколькими способами. Возьмите частное с обоих концов и вычтите их: 28 - 14 = 14. Или возьмите разницу двух конечных точек, разделите на делитель и добавьте 1: 196 - 105 = 91, 91 / 7 = 13, 13 + 1 = 14. Но будьте осторожны, когда одна из конечных точек делится на делитель; Я оставлю это вам, чтобы проработать детали, а также написать программу.
public static int solution(int low,int high, int n) {
boolean h0=high%n==0;
boolean l0=low%n==0;
int k1=l0?low/n:(low+n-low%n)/n;
int k2=h0?high/n:(high+n-high%n)/n;
// |-----------|
// ---------------k1----------k2---------------
if(k2*n>high) k2--;
return k2-k1+1;
}
Вместо того, чтобы перебирать каждый номер, вы можете попробовать
public int test(int floor, int ceil, int n) {
int a = (floor / n) + 1;
int counter = 0;
while (a * n <= ceil) {
counter++;
a++;
}
return counter;
}
и использовать только кратные делителя. Теперь вы не делаете повторное деление (медленно), вы делаете повторное умножение (быстрее).
Ну, я не профессор университета, поэтому у меня нет для вас какой-то удивительной формулы, но на самом деле, насколько мне известно, единственный способ проверить список чисел, подобный этому, - это перебрать их, в конце концов, вы получите нужно оценить переменную, чтобы проверить, делим ли она, теперь есть способ оптимизировать ваш алгоритм, сначала отсортировать числа! Изначально это будет дорого, но любые последующие проверки номеров будут выполняться намного быстрее,
Я предлагаю взглянуть на алгоритмы сортировки, я бы использовал пузырьковую сортировку, которая появится в Google довольно часто.
Что касается того, что вы можете сделать с сортировкой, вы могли бы отсортировать числа в списки кратных, например, 2 4 6 8 все кратны 2, так что вы можете в основном проверить первое в списке, а остальные будут сразу же известны также быть делимым
Имейте в виду, что может быть гораздо более эффективный способ сделать это, просто предлагая мои 2 цента