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 