Geek asks and answers

Optimize the code to get the number of integers in a given range that are divided by integers

This range is x, y. I need to count all the numbers between them and divide by n.

I know that an easy way to do this is to loop across the entire range

for(int i=x;i<=y;i++) if(i%n ==0) counter++;

The counter contains the answer.

But it works so slowly for large ranges. e.g. x = 0, and y = 3,000,000,000.

I'm sure there is some relation that I can use to reduce the number of iterations and optimize this code for speed. I searched, but I could not find him. Can someone help me with this please.

Many thanks.

+5
source share
10 answers

: (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).

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

:

a/d, d 0 a. (!= 0)

, () (/) - () (/) , (, ) ( , , )

, , (% d == 0)

fmodf .

+2

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

, :

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

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

. (), ().

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

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

-1

: , [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);

}
-1
 public int myfunc(int low, int high, int test) {   
    int count = 0;
    if(low % test == 0)
       count++;
    count +=(high-low)/test;
    return count;
 }
-1

, , - , , , - , , , , , ! , ,

I suggest looking at the sorting algorithms, the one I would use would look like a bubble, which will go a bit on google.

As for what you can do when sorting, you can sort numbers into lists from multiple numbers, for example, 2 4 6 8 all multiples of 2, so that you can basically check the first in the list and the rest is instantly also known as the dividend

Keep in mind that there can be a much more efficient way to do this by simply offering my 2 cents.

-2
source

More articles:


All Articles