Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Multiples within interval

Tags:

algorithm

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.

like image 608
Daniel Avatar asked Sep 20 '26 09:09

Daniel


1 Answers

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.

like image 163
zw324 Avatar answered Sep 23 '26 15:09

zw324



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!