CODEWITHSUNDEEP
javac++mathdivision
Coder Stacker
Coder Stacker

Reputation: 53

optimize code to get the number of integers within given range that are divisible by integer

Given range x, y. I need to count all numbers in between and are divisible by n.

I know the simple way to do this is by looping over the whole range 

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

The counter holds the answer.

But this works so slow for big ranges. for example x=0 , and y=3,000,000,000.

I'm sure that there is some relation that I can use to reduce the number of iteration and optimizing this code for speed. I searched but i could not find it out. Can any one help me with that please.

Thanks so much.

Upvotes: 5

Views: 5870

Answers (10)

Roman Malieiev
Roman Malieiev

Reputation: 305

Only this implementation works for me (A, B in [0..2kkk]; K in [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;
}

Upvotes: 0

cegprakash
cegprakash

Reputation: 3125

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

Explanation:

There are a/d numbers divisible by d from 0 to a. (d!=0)

Therefore (floor)(high/d) - (floor)(low/d) will give numbers divisible in the range (low,high] (Note that low is excluded and high is included in this range)

Now to remove high from the range just subtract (high%d==0)

Use fmodf for floats.

Upvotes: 2

vandervagos
vandervagos

Reputation: 113

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

Upvotes: -1

Raman Buzaubakov
Raman Buzaubakov

Reputation: 503

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;

}

Upvotes: -1

Eric Postpischil
Eric Postpischil

Reputation: 222763

This works: (e+1 - s) / d + (e%d < (s+d-1)%d). (It uses C semantics and integer arithmetic and assumes the start is non-negative. s is the start value, e is the end value [inclusive], and d is the divisor.)

Updated: A better solution is e/d - (s-1)/d. This was inspired by User448810. That requires s be positive; handling zero or negative s (or e) requires adjusting for the truncation toward zero (we would want toward negative infinity for this problem).

Update for negative values: The following works for any values of s and e in the range of their types, provided s <= e and 0 < d:

e = e <  0 ? (e+1)/d - 1 : e/d;
s = s <= 0 ? s/d - 1 : (s-1)/d;
return e-s;

Essentially, the first two statements are equivalent to e = e/d and s = (s-1)/d with the division modified to round toward -infinity instead of toward zero (so that -1/10 produces -1 rather than 0).

Upvotes: 7

Gaurang
Gaurang

Reputation: 144

Kindly provide comments on algorithm below: Suppose the range is [R1,R2] and number to be divided is n.

Find the smallest number starting from R1 divisible by n.Call it small.

Find the largest number starting from R2 divisible by n. Call it large.

Total numbers that are divisible= (large-small)/n + 1.

Worst case is still O(n) but might be efficient for large difference between R1 and R2.Hopefully I have covered all cases. Kindly suggest.

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

}

Upvotes: -1

user448810
user448810

Reputation: 17874

You asked for a count of the number of integers between x and y (both x and y are included in the range) that are divisible by n. There is no need for any looping, and only two divisions are necessary to compute the answer. Let's consider a simple example: for the range 100 to 200, how many integers are divisible by 7?

Start at the low end of the range: 100 / 7 = 14 with a remainder of 2. Now the divisor 7 minus the remainer 2 is 5, so the smallest number on the range that is divisible by 7 is 100 + 5 = 105.

Now go to the high end of the range: 200 / 7 = 28 with a remainder of 4, so the largest number on the range that is divisible by 7 is 200 - 4 = 196.

Thus, the numbers on the range that are divisible by 7 are 105, 112, 119, 126, 133, 140, 147, 154, 161, 168, 175, 182, 189, and 196. There are 14 of them, which you can calculate in a couple of ways. Take the quotient at both ends and subtract them: 28 - 14 = 14. Or take the difference of the two endpoints, divide by the divisor, and add 1: 196 - 105 = 91, 91 / 7 = 13, 13 + 1 = 14. But be careful when one of the endpoints is divisble by the divisor; I'll leave it to you to work out the details, and also to write the program.

Upvotes: -1

Peter
Peter

Reputation: 1359

I'm pretty sure you can do this:

public static int numDivisible(int low, int high, int test) {
    return (high-low)/test;
}

There you go. A constant-time solution. Since you don't need to know exactly which numbers are divisible, you don't need to bother iterating through all of them.

EDIT: Change this to the following, as per @Chaser324.

public static float numDivisible(float low, float high, float test) {
    return Math.ceil((high-low)/test);
}

EDIT: A small typo ie., changed text to test

Upvotes: -1

gobernador
gobernador

Reputation: 5739

Rather than iterating over each and every number, you could try

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

and only use multiples of the divisor. Now you're not doing repeated division (slow), you're doing repeated multiplication (faster).

Upvotes: -1

user1294021
user1294021

Reputation: 322

Well, I am not a university professor so I don't hold some amazing formula for you, but really as far as I know the only way to check over a list of numbers like that is to iterate over them, in the end you will have to evaluate the variable to check wether it is divisible, now there is a way to optimise your algorithm, sort the numbers first! This will initially be expensive, but any successive needs to check the numbers would be much faster,

I suggest looking at sorting algorithms, the one I would use would be bubble sort, which will come up on google quite a bit.

As for what you can do with the sorting, you could sort numbers into lists of of multiples, for instance 2 4 6 8 are all multiples of 2 so you could basically check the first in the list, and the rest would be instantly known to also be divisible

Keep in mind there may be a much more efficient way of doing this, just offering my 2 cents

Upvotes: -2

Related Questions