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.

Pages: 1 2

15 Responses to “Number Of Divisors In A Range”

  1. Andras said

    Maybe (y-x)/n ?

  2. Andras said

    ok, it is not that easy :)

  3. mvaneerde said

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

  4. Andras said

    mvaneerde: you are right.

    In Scala:

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    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))
    	}
    }
    
  5. Jussi Piitulainen said

    I think the following makes the length of a Python range object to give the answer.

    >>> x, y, n = 100, 200, 7 ; len(range(-(-x // n) * n, y, n)) - (x % n == 0)
    14
    

    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.

  6. Pravinth said

    (y%n – x%n) ?

  7. HariKrishna said

    floor((y-x)/n) when x 0. This should work !!

  8. kbob said

    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.

  9. programmingpraxis said

    @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.

  10. matthew said

    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)

  11. matthew said

    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)
    
  12. matthew said

    Also, this needs some slight modification for languages like C++ where x%n might be negative.

  13. Claire said

    counter = (y/n -x/n)

  14. Claire said

    Sorry ,it becomes incorrect if x is divisible by n. So it should be like this: counter = y/n -x/n + (x%n == 0);

  15. Jason said

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: