Skip to main content

A Codility Wake-Up Call

· 5 min read
Irving Dinh

I took a Codility test today. Three problems, 90 minutes. It went okay — all tests passed — but my solutions weren't optimal. Time to get back to LeetCode.

Here's a breakdown of the problems, my solutions, and the optimal approaches I should have used.

Problem 1: Double Digit Sum​

The problem: Given an integer N, find the smallest number M > N where the digit sum of M equals double the digit sum of N.

Example: Input 14 → digit sum is 1+4=5, doubled is 10, so find the smallest number > 14 with digit sum = 10 → output is 19 (because 1+9=10).

My Solution: Brute Force​

I went with the straightforward approach — start from N+1 and check each number until I find one with the target digit sum.

def solution(n):
    target = 2 * digit_sum(n)
    candidate = n + 1
    while digit_sum(candidate) != target:
        candidate += 1
    return candidate

def digit_sum(x):
    total = 0
    while x > 0:
        total += x % 10
        x //= 10
    return total

Time complexity: O(M × D) where M is the gap between N and the answer, and D is the number of digits. This works fine for small inputs, but could get slow for larger digit sums.

The Optimal Approach: Direct Construction​

Instead of searching, we can construct the smallest number with a given digit sum directly. The trick is to use as few digits as possible (smaller number of digits = smaller number), and maximize digits from the right (put 9s on the right, remainder on the left).

def solution(n):
    target = 2 * digit_sum(n)
    return smallest_with_digit_sum(target)

def smallest_with_digit_sum(s):
    if s == 0:
        return 0
    nines = s // 9
    remainder = s % 9
    if remainder == 0:
        return int('9' * nines)
    else:
        return int(str(remainder) + '9' * nines)

Example: Target sum = 10 → 10 // 9 = 1 nine, 10 % 9 = 1 remainder → answer is 19.

Time complexity: O(D) — just construct the number directly.

The pattern: This is a "construct smallest/largest number with constraints" problem. The greedy insight is to minimize the number of digits first, then fill with 9s from the right.

Problem 2: Maximize Number by Adding K to Digits​

The problem: Given a 3-digit integer N and a budget K, maximize N by distributing K across its digits. You can add to any digit, but can't exceed 9 per digit.

Example: N = 247, K = 10 → output is 977.

My Solution: Greedy Left-to-Right​

This one I got right! The key insight: leftmost digits have the highest place value, so maximize them first.

def solution(n, k):
    digits = [int(d) for d in str(n)]

    for i in range(len(digits)):
        cost_to_9 = 9 - digits[i]
        if k >= cost_to_9:
            digits[i] = 9
            k -= cost_to_9
        else:
            digits[i] += k
            k = 0
            break

    return int(''.join(map(str, digits)))

Walkthrough for N=247, K=10:

  • Digit 2: needs 7 to become 9, spend 7 (K=3 left) → digit becomes 9
  • Digit 4: needs 5 to become 9, but we only have 3, so add 3 (K=0) → digit becomes 7
  • Digit 7: no budget left → stays 7
  • Result: 977

Time complexity: O(D) — one pass through the digits.

The pattern: This is the "budget allocation" pattern. You have a limited resource and want to maximize impact by prioritizing high-value positions. Always ask: "What gives me the most bang for my buck right now?"

Problem 3: Minimum Swaps to Group Elements​

The problem: Given a string of W's and R's (white and red balls), find the minimum number of adjacent swaps to group all R's together.

Example: "WWRWRRW" → find minimum swaps to get all R's adjacent.

My Solution: Median-Based Approach​

I found all the R positions, computed the median, and summed the distances to the median.

def solution(s):
    r_positions = [i for i, c in enumerate(s) if c == 'R']
    if len(r_positions) <= 1:
        return 0

    median_idx = len(r_positions) // 2
    median = r_positions[median_idx]

    swaps = 0
    for i, pos in enumerate(r_positions):
        # Adjust for stacking: each R needs its own slot
        target = median - (median_idx - i)
        swaps += abs(pos - target)

    return swaps

The trick is accounting for the "stacking effect" — when multiple R's move toward the center, they can't all occupy the same position. Each R needs its own slot, so we adjust the target position for each one.

Time complexity: O(N) — one pass to find positions, one pass to compute swaps.

The pattern: This is a "minimum swaps to group elements" problem, related to counting inversions. The median minimizes the total distance for meeting points, but you need to adjust for elements that will be adjacent in the final state.

It passed all tests, but I wasn't 100% confident in my reasoning. The more standard approach uses two pointers:

Alternative: Two Pointers​

def solution(s):
    left, right = 0, len(s) - 1
    swaps = 0

    while left < right:
        while left < right and s[left] == 'W':
            left += 1
        while left < right and s[right] == 'W':
            right -= 1
        if left < right:
            # Count W's between these two R's
            swaps += s[left:right].count('W')
            left += 1
            right -= 1

    return swaps

Process from both ends, moving outer R's toward the center, counting the W's that need to be swapped past.

The Wake-Up Call​

All three problems passed, but I wasn't happy with my performance:

  1. Problem 1: Brute force works but isn't elegant. I should've recognized the "construct optimal number" pattern immediately.

  2. Problem 2: Got this one clean. Greedy left-to-right is the right approach.

  3. Problem 3: My solution worked, but I wasn't confident in the reasoning. I need to drill the two-pointer and median patterns more.

Key patterns to practice:

  • Greedy construction (building optimal numbers digit by digit)
  • Budget allocation (maximizing value with limited resources)
  • Two pointers for array/string optimization
  • Median for minimizing total distance

Time to get back on LeetCode. The rust is real.