Solving a “Respectable” Codility Challenge in One Line of Code

Keeping things simple and efficient.

Photo by Joshua Aragon on Unsplash

Contents

∘ The Task
∘ Understanding the Challenge
∘ Iterating in Steps
∘ A Set of Basic Mathematical Operations
∘ Porting to Python
∘ References

I really like Codility challenges. They’re a wonderful (and totally free) way to improve your problem-solving skills and programming language knowledge. They’re also a great way to “warm-up” your brain for technical interviews, especially since most of your solutions are evaluated on their ability to handle edge cases while remaining time-efficient.

Much of modern professional development consists of configuring and chaining libraries together, so it’s refreshing to get to sink into a task that’s purely logic and performance-based.

Over the past couple of years, I’ve been slowly working through their lessons and challenges on weekends and holidays and it’s helped me to retain a mindset of looking for “greedy algorithm” solutions and considering both performance and readability.

One particular lesson took me by surprise. Codility tasks are rated, in order of difficulty, as “Painless,” “Respectable,” or “Ambitious.” This task was rated “Respectable” but it is efficiently solvable with a single line of code.

The Task

Codility lessons are comprised of reading material in a PDF and a set of “tasks.” The first task in the “Prefix Sums” lesson is called “Count Div.” The instructions are:

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

We are guaranteed that A ≤ B.

Understanding the Challenge

To gain a more complete view of a problem, I sometimes find it useful to sketch it out without worrying at all about efficiency.

An obvious brute-force solution would be to iterate through all the integers between A and B checking if they are divisible by K using modulo (%).

To be safe we also need to check that B != 0. In ruby:

def solution(a, b, k)
  return 0 if b == 0
  count = 0
  (a..b).each do |ii| 
    count += 1 if ii % k == 0
  end
  count
end

Or, much more concisely, using the ternary operator and filterto give us a count (size) of all numbers that fit our criteria:

def solution(a, b, k)
  b == 0 ? 0 : (a..b).filter{ |ii| ii % k == 0 }.size
end

This will run in linear time — O(n)— which is less than ideal if A is 0 and B is the test’s possible maximum value of 2 billion.

Iterating in Steps

Similarly, as in the example below, finding the smallest and largest multiple of k in the range of A to B and iterating in steps equal to K still leaves us with O(n)— particularly inefficient if K is 1.

def solution(a, b, k)
  return 0 if b == 0 || k > b
  first_divisible = a % k == 0 ? a : a + (k - a % k)
  last_divisible = b - b % k
  (first_divisible..last_divisible).step(k).size
end

But we’re close to an efficient solution. We can now see that all we need to see is how many times multiples of K occur between A and B.

A Set of Basic Mathematical Operations

Let’s use the original example from Codility, a = 6, b = 11, k = 2

• 11 / 2 = 5.5 — which we can round down to 5 to give the total number of ways that 2 goes evenly into 11
• (6 - 1) / 2 = 2.5 — which we can round down to 2 for the number of ways ints less than 6 are evenly divisible by 2. We can subtract these from the total above.
• 5 - 2 = 3 — subtract the excluded count from the total to get our result.

In ruby, dividing one integer by another will automatically round down the quotient, returning an integer result. This makes our solution both tidy and efficient, running in O(1) constant time.

def solution(a, b, k)
  b / k - (a - 1) / k
end

The edge cases where A and/or B are zero are also neatly handled by the rounded-down division.

Porting to Python

Python’s floor division (“//” operator) can also handle this operation for us, although we still need to check if B is 0.

def solution(a, b, k):
    return 0 if b == 0 else int(b // k - (a - 1) // k)

Either of these last two examples will still get a 100% result on Codility.

Please let me know if anything here doesn’t make sense or if you can think of an even more concise way to achieve this result.

References

Codility Prefix Sums lesson

// floor division - Python Reference (The Right Way) 0.1 documentation