Number Of Divisors In A Range
October 28, 2014
We have today an interview question that was posted to the internet by a candidate who didn’t get the job, and wondered what he had done wrong. I’ll paraphrase his question:
The interview question was to find the number of integers between x and y that are divisible by n; you may assume that x, y and n are all positive and that x < y. I know the simple way to solve this is to loop over the range from x to y, like this:
for(int i=x;i<=y;i++) if(i%n ==0) counter++;but that is very slow when the range is large, for instance x = 0 and y = 3000000000.
There must be some method that lets me reduce the number of iterations and optimize the code. Can someone please help me with that?
Your task is to help the candidate get the job by proposing a better algorithm to solve the problem. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Maybe (y-x)/n ?
ok, it is not that easy :)
Let #(n, x, y) be the number of multiples of n in the range [x, y] inclusive.
#(n, 1, y) is easy; this is just floor(y/n).
The trick is to realize that #(n, x, y) = #(n, 1, y) – #(n, 1, x – 1).
mvaneerde: you are right.
In Scala:
object NumberOfDivisorsInARange { def dummy(n:Int, x:Int, y:Int):Int = { (for(a <- x to y if a%n==0) yield 1).sum } //> dummy: (n: Int, x: Int, y: Int)Int def smart(n:Int, x:Int, y:Int):Int = { y/n - (x-1)/n } //> smart: (n: Int, x: Int, y: Int)Int for(n<- 1 to 20; x <- 1 to 50; y <- x to 60 if smart(n,x,y) != dummy(n,x,y)){ println((n,x,y)+" "+smart(n,x,y)+" "+ dummy(n,x,y)) } }I think the following makes the length of a Python range object to give the answer.
I used ceiling division in terms of flooring division to adjust the lower bound of the range, and an Iversonian adjustment to exclude the original lower bound from the count if it happened to be included. I think this handles negative bounds. I was disappointed to find that len does not cope with large bounds. Empty ranges would require a further adjustment but the problem statement promised distinct bounds.
(y%n – x%n) ?
floor((y-x)/n) when x 0. This should work !!
That is a great interview question. Simple, useful, and somewhat harder than it first appears.
count = y // n # // is integer division, truncates toward zero when both operands are positive
if x != 0: count -= (x – 1) // n
return count
That’s fairly concise and readable, and it requires at most two divides.
@kbob: Agreed. It is a great interview question. First, there’s the matter of the side-track that the candidate in the story followed. Second, there are some obvious wrong answers, which give you the chance to see how the candidate responds to a malicious test case. Third, there is a good follow-up that makes things tougher: remove the restriction on positive integers. It’s simple, but offers surprising depth, and ought to clearly show differences among a range of candidates.
Nice little problem. Here’s a solution that I think deals with negative numbers properly (also, like the OP, it includes the endpoints in the count if they are divisors). We shift the range so that 0 <= x < n, then y//n gives the number of (non-zero) divisors <= y, and we add an extra 1 on (using Jussi's "Iversonian adjustment") if the start point is now at 0.
def f(x,y,n):
(x,y) = (x%n,y-x+x%n)
return y//n + (x==0)
Something happened to the formatting there, but I don’t know what, try again:
def f(x,y,n): (x,y) = (x%n, y-x+x%n) return y//n + (x==0)Also, this needs some slight modification for languages like C++ where x%n might be negative.
counter = (y/n -x/n)
Sorry ,it becomes incorrect if x is divisible by n. So it should be like this: counter = y/n -x/n + (x%n == 0);
The trick I utilized lies in the realization that modulus is clock arithmetic, it’s a skip count, and for loops can skip count. At each skip (i+n), you can just increment the counter. The hard part is finding the starting point of our loop. If n is greater than x, this is relatively easy. If x is 0, just increment the counter once, but whether it is or not, we want to start at n (because, other than 0, that’s the first number that would be divisible by n in our range). If, on the other hand, n is less than x it’s a bit trickier, but only a bit. Let’s say that the range is 11 to 37 and we want to find how many are divisible by 5. 11%5 = 1 (and 12%5 = 2, 13%5 = 3, and so on…) I need to add 4 to 11, that’s 5 – 1, and the pattern works for any other case, so our general formula is: x + (n – (x % n)). The following java snippet will illustrate:
int cnt = 0;
if (n >= x) {
if (x == 0) cnt++;
for (int i = n; i <=y; i += n) cnt++;
} else for (int i = x + n – x % n; i <=y; i += n) cnt++;
return cnt;
I ran this with n = 20, x = 0, and y = 300000000, comparing it to the interviewee's solution. His took about 7 seconds to run, mine takes less than a second, but running them both confirms that it's accurate every time.