Find Minimum Operations to Make All Elements Divisible by Three - Video Solutions

Problem Overview: You get an integer array. In one operation you can increment or decrement any element by 1. The goal is to make every value divisible by 3 using the minimum number of operations.

The key observation: divisibility by 3 depends only on the remainder when dividing by 3. If num % 3 == 0, the element already satisfies the requirement. If the remainder is 1 or 2, you adjust the number by the shortest distance to the nearest multiple of 3.

Approach 1: Modulo and Adjustment (O(n) time, O(1) space)

Iterate through the array and compute r = num % 3. If r == 0, no operation is required. If r == 1, you can subtract 1 to reach the previous multiple of 3. If r == 2, you can add 1 to reach the next multiple of 3. Each non‑zero remainder therefore costs exactly one operation. Accumulate the number of such adjustments while scanning the array once.

This works because multiples of 3 are spaced exactly three units apart. Any number with remainder 1 or 2 is always one step away from some valid multiple. The algorithm uses simple arithmetic and a single pass over the array, which keeps the implementation clean and efficient. Since only a few integer variables are used, the extra space remains constant.

Approach 2: Array to Direct Count (O(n) time, O(1) space)

This approach focuses purely on counting remainders. Traverse the array and classify each element by num % 3. Maintain counters for remainder 1 and remainder 2. Each occurrence contributes one operation because you either decrement a remainder‑1 number or increment a remainder‑2 number.

After processing the entire array, the total operations equal count1 + count2. The logic is slightly more explicit than the previous approach and can be helpful when reasoning about groups of elements rather than individual transformations.

Both approaches rely on modular arithmetic and sequential iteration, common techniques when working with array problems that involve divisibility or remainder patterns in math-based logic.

Recommended for interviews: The modulo adjustment approach. It shows you immediately recognized the remainder pattern and converted the problem into a simple linear scan with constant space. The counting variant demonstrates the same insight but is slightly more verbose. Interviewers typically expect the O(n) pass using num % 3.