Smallest Missing Multiple of K - Solution & Explanation

Problem Overview: You are given an integer array and a value k. The task is to find the smallest positive multiple of k that does not appear in the array. In other words, check multiples k, 2k, 3k... and return the first one missing from the input.

Approach 1: Brute Force Enumeration (O(n^2) time, O(1) space)

Start from the first multiple k and repeatedly check if that value exists in the array. Each check requires scanning the entire array. If k exists, move to 2k, then 3k, and continue until a multiple is not found. The nested work comes from enumerating multiples while performing a full array search for each candidate. This approach works for very small inputs but becomes slow as the array grows because every membership check costs O(n).

Approach 2: Hash Table + Enumeration (O(n) time, O(n) space)

Store all numbers from the array in a hash set. This enables constant-time membership checks. After building the set, enumerate multiples of k starting from k. For each multiple, perform a hash lookup. The first multiple not present in the set is the answer. If the array contains k, 2k, 3k ... mk, the algorithm returns (m + 1) * k. The key insight is replacing repeated linear scans with O(1) lookups using a hash structure.

This technique is common when solving presence or frequency problems in Array tasks. A hash-based structure dramatically reduces lookup cost compared to repeated scanning. Problems involving membership queries or duplicate detection typically benefit from a Hash Table.

Recommended for interviews: The hash table + enumeration solution is the expected approach. Interviewers want to see that you recognize repeated lookups and replace them with constant-time hash checks. Mentioning the brute force approach first shows problem understanding, but implementing the hash-based solution demonstrates practical optimization skills.