Number Of Divisors In A Range
October 28, 2014
The solution, of course, is not to loop at all. Instead, we take the length of the range, divide by the number, and adjust for the case where one or the other (or both) ends of the range are divisible by the number.
Consider the case with x = 100, y = 200, and n = 7. The smallest multiple of 7 in the range is 105, the largest multiple of 7 in the range is 196, and there are 12 other multiples of 7 between them — 112, 119, 126, 133, 140, 147, 154, 161, 168, 175, 182, and 189 — giving a total of 14 divisors.
The only hard part is making sure that you properly handle the case where one (or both) of the limits is divisible by n. For instance, with x = 100 and y = 200, as before, but n = 40, the correct answer is 2, for the numbers 120 and 160 but not 200; we’ll write that f(100,200,40) = 2. There’s also the case where both limits are multiples of n: f(100,200,10) = 9. Don’t forget the case where the lower limit is divisible by n but the upper limit is not: f(105,200,7) = 13; remember that we want multiples between the limits. And of course it is possible for there to be no multiples between the limits: f(105,112,7) = 0.
Here’s our solution:
(define (f x y n)
(- (quotient (- y 1) n)
(quotient x n)))
And here are some examples:
< (f 100 200 7)
14
< (f 100 200 40)
2
< (f 100 200 10)
9
< (f 105 200 7)
13
< (f 105 112 7)
0
That’s trickier than it looks. And it gets even worse if you allow x and/or y to be negative, because rounding goes the wrong way; for instance, f(-200, -100, 40) = 2, -160 and -120, but our solution gives 3. Fortunately, we specifically assumed both x and y were positive.
You can run the program at http://programmingpraxis.codepad.org/bic9XZPm.
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.