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

Stuart McLean
Jun 16 · 4 min read

Keeping things simple and efficient.

Contents

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

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

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

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

  • 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

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

Geek Culture

Proud to geek out. Follow to join our 1M monthly readers.