The Weekly Challenge 049

Smallest Multiple and LRU Cache

Solutions on GitHub

Task 1: Smallest Multiple

Write a script to accept a positive number N and print the smallest multiple of N consisting only of digits 0 and 1.

Example Output

Input: 55 Output: 110

Logic

Perform a Breadth-First Search (BFS) over remainder modulo N to find the shortest string representation containing only 0 and 1 that results in a remainder of 0.

Perl Solution

ch-1.pl

sub find_multiple_0_1 { my $input = shift; my $count = 0; while ($input !~ /^[01]+$/) { $input += $input; return -1 if $count == 1000; $count++; } return $input; }

Python Solution

ch-1.py

def smallest_multiple_01(n: int) -> str: start = 1 % n if start == 0: return "1" parent = {start: -1} digit = {start: "1"} q = deque([start]) while q: r = q.popleft() for d in ("0", "1"): nr = (r * 10 + (1 if d == "1" else 0)) % n if nr in parent: continue parent[nr] = r digit[nr] = d if nr == 0: out = [] cur = nr while cur != -1: out.append(digit[cur]) cur = parent[cur] return "".join(reversed(out)) q.append(nr)

Task 2: LRU Cache

Write a script to demonstrate LRU (Least Recently Used) Cache feature, supporting `get` and `set` operations with a defined capacity.

Logic

Use an ordered structure (like Cache::LRU in Perl or OrderedDict in Python) to keep track of access order. Move recently accessed keys to the end and discard the oldest keys when capacity is exceeded.

Perl Solution

ch-2.pl

use Cache::LRU; my $cache = Cache::LRU->new( size => $size ); $cache->set(1=>3); $cache->set(2=>5); $cache->get(2); # returns 5

Python Solution

ch-2.py

from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self._capacity = capacity self._data = OrderedDict() def get(self, key): if key not in self._data: return None self._data.move_to_end(key) return self._data[key] def set(self, key, value): if key in self._data: self._data.move_to_end(key) self._data[key] = value if len(self._data) > self._capacity: self._data.popitem(last=False)