In the same discussion that I referenced in this post; I was asked the following: “Write a function, that, given three integers A, B and K, returns the number of integers within the range [A..B] that are divisible by K.” The idea being that if I had A=12; B=19, and K=6, it would produce the answer “2” because 12 is evenly divisible by 6, and the only other number in that range that is evenly divisible by 6 is 18. I had 30 minutes to write my answer. Initially, my 12 year old memory of my Discrete Math class let me down and I couldn’t remember the shortcut to do this. I would have Googled the answer, because I knew there was a trick, but I was concerned about academic honesty. My first approach was an algorithm that looked like this:

`public int count_div(int A, int B, int K)
{
int retval=0;
for(int i=A;i<=B;i++)
{
if(i%K==0)
{
retval++:
}
}`

return retval;

return retval;

}

}

Quick to write, easy to understand, brute force answer. However, when the range was very large (A=1, B=100,000,000) it timed out. OK, the answer boiled down to remembering my Discrete Mathematics class from 2000. With about 8 minutes to spare, I finally finished puzzling out the answer of “Well really, it would be dividing B by K, minus A by K”. So, my next pass was the following:

`public int count_div(int A, int B, int K)
{
int a;
if(A==0)
{
a=1;
}
else
{
a=A;
}
return (B/K)-(a/K);
}`

I was nervous because this was an interview, I was running short of time, and made the trivial mistake of thinking “If A is zero, this won’t produce the right answer”. Of course, as you can guess it still didn’t produce the right answer. However, I’d solved the speed issue. I entered a few test cases and changed it to the following.

`public int count_div(int A, int B, int K)
{
int a;
if(A==0)
{
a=1;
}
else
{
a=A;
}
return (B/K)-(a/K)+1;
}`

Again, still wrong, but I didn’t have time to throw test cases at it to determine the full extent my wrongness. For some reason, the interviewer accused me of creating 2 variables, when I’d only created a single variable. I think he’d pretty much written me off and didn’t look at the answer nor care how close I was to the correct answer. *While this didn’t produce the correct answer, I was very close*. The problem I was running into boiled down to (12, 19, 6) and (13, 20, 6) do not give the same answer, despite the same range. That “+1” ended up messing me up even more than the a=1 from a purely logical perspective. In hindsight, I sat back, and checked my work and kicked myself at how close my answer was.

`public int count_div(int A, int B, int K)
{
return (B/K) – (A/K) + (A%K == 0 ? 1: 0);
}`

Does this work? We can look to Software Quality Assurance knowledge and do a little equivalence partitioning to test it with a minimal number of cases. Equivalence Paritioning is when you divide the input data into “partitions” of data to create test cases. While this makes some assumptions, it can drastically reduce the number of test cases being developed. In the cartesian product of possible cases, the below cases handles the four basic situations that should appear. We know that the C# math functions generally work, so we shouldn’t need to test those.

Test Case 1: A = 6, B=11, K = 3

This case represents when A is counted in the answer, and B is not.

This case produces “2” because

`(11/3) – (6/3) + (6%3 == 0 ? 1 : 0) = 3 – 2 + 1 = 2.`

Test Case 2: A = 7, B = 12, K= 3

This case represents when B is counted in the answer, and A is not

This case produces “2” because

`(12/3) – (7/3) + (7%3 == 0 ? 1 : 0) = 4 – 2 + 0 = 2.`

Test Case 3: A = 7, B = 11, K = 3

This case represents when neither A nor B are counted in the answer

This case produces “1” because

`(11/3) – (7/3) + (7%3 == 0 ? 1 : 0) = 3 – 2 + 0 = 1.`

Test Case 4: A=6, B=12, K = 3

This case represents when both A and B are counted in the answer

This case produces “3” because

`(12/3) – (6/3) + (6%3 == 0 ? 1 : 0) = 4 – 2 + 1 = 3.`

Now, after about an hour of work (counting the original interview time but not counting writing this post) I have come up with the correct answer and created 4 possible unit tests to verify the code works.

Thoughts? Comment below!

October 16, 2012 at 5:43 pm

Note that the speed of the "fast answer" is entirely dependent upon coming up with a formula for the answer instead of an algorithm. In real life, if you have to rely on a developer to come up with a fancy formula to optimize an algorithm, you're doing it wrong. (http://xkcd.com/463/) No one will be able to trust the algorithm, and worse, no one will be able to maintain it, especially should the algorithm prove to be incorrect on some particular edge case. Think of the Pentium division error.

As for how to come up with a useful algorithm, in this case, the key thing to realize is that the answer is going to be "close to" the integer part of (B-A)/K … that is to say, if you start from 0, and count all the even multiples up to B-A, that is the same as starting at whatever A is and counting them up to B. At that point, one just needs to realize the edge case, as you do in your final version of the algorithm: that if the endpoints of the range are EVENLY divisible by the number, (B-A)/K is going to undercount by one.

That said, this is the kind of coding one does for embedded projects, on chips, taking advantage of all the dirty tricks you can to gain performance from doing things smarter. In normal software projects, the bang for the buck is miniscule. Any real life project that needs to deal with 100,000,000 items is going to bog down from the sheer mass of data, and there will be no nifty trick to count items of a particular property that doesn't involve some kind of indexing (database or otherwise).

October 18, 2012 at 1:22 pm

Thanks James.

You are very good at putting things like this into perspective. The more I think about that particular set of coding exercises, the more I realize it really wasn't the job for me.