CODEWITHSUNDEEP
algorithm
Daniel
Daniel

Reputation: 7724

Multiples within interval

Given a number n and some interval (L : R), how can I count the multiples of n within this interval?

If I do (R-L+1)/n, it won't give me right answer, cos for example, within 3 and 5, there are one multiple of 4, but (5-3+1)/4 = 0, within 4 and 8, there are 2 multiples of 4, but (8-4+1)/4 = 1.

I tried this but it wont work too (fail in div(4,4,13) = 2 )

int div(int n, int l, int r){
    let mod = n - l % n;
    let first = mod == n? l : l + mod;
    return first > r? 0 : (r-first+1)/n + 1;
}

the point is: I don't wanna check a thousand things, I guess there's some fast way to do it.

Upvotes: 3

Views: 386

Answers (1)

zw324
zw324

Reputation: 27210

Wouldn't

R/n - (L-1)/n

work assuming integer divisions here? Since R/n is the number of multiples of n <= R, and (L-1)/n the number of multiples of n < L, the difference is what you want.

Upvotes: 1

Related Questions