3937. Minimum Operations to Make Array Modulo Alternating I

MediumArrayEnumeration

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums and an integer k.

In one operation, you can increase or decrease any element of nums by 1.

An array is called modulo alternating if there exist two distinct integers x and y (where 0 <= x, y < k) such that:

For every even index i, nums[i] % k == x
For every odd index i, nums[i] % k == y

In simpler terms, all elements at even positions must have the same remainder x when divided by k, and all elements at odd positions must have the same remainder y when divided by k. The two remainders x and y must be different from each other.

Your task is to return the minimum number of operations required to make nums modulo alternating.

Note that when adjusting an element to reach a target remainder, you can move in either direction around the modulo cycle. For example, if an element has remainder v and you want it to have remainder target, the cost is the smaller of the direct difference abs(target - v) and the wrap-around difference k - abs(target - v), since increasing or decreasing past a multiple of k wraps the remainder around.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Greedy Algorithms?

This problem maps to Greedy Algorithms through a short path in the full flowchart.

Making the locally optimal choice at each step produces the globally optimal result.

Open in Flowchart

Intuition

The key observation is that the final state of the array is determined entirely by just two values: the target remainder x for all even indices and the target remainder y for all odd indices. Once we fix x and y, every element has a clear target, and the cost to adjust each element becomes independent of the others.

Since both x and y must lie in the range [0, k), there are only k possible choices for x and k possible choices for y. This means the total number of valid (x, y) pairs is small enough (at most k * k) to simply try them all and pick the best one.

For any single element with remainder v, the cost to turn it into a target remainder target is not just abs(target - v). Because the values live on a modulo cycle of size k, we can move around the cycle in either direction. Moving directly costs abs(target - v), but wrapping around the other way costs k - abs(target - v). We always take the cheaper of these two, so the per-element cost is min(abs(target - v), k - abs(target - v)).

Putting these ideas together, the strategy becomes natural: first reduce every element to its remainder modulo k, then enumerate every distinct pair (x, y). For each pair, sum up the minimal cost of converting each element to its respective target (x for even indices, y for odd indices), and keep track of the smallest total cost across all pairs. The constraint that x and y must be distinct is enforced by skipping pairs where x == y.

Solution Approach

Solution 1: Enumeration

The implementation follows directly from the intuition. We enumerate the target value x for even indices and the target value y for odd indices, where 0 <= x, y < k and x != y. For each element, we calculate the number of operations required to change it to its target value, accumulate the total, and finally return the minimum value among all enumeration results.

Step 1: Normalize the array.

Before doing anything else, we replace every element with its remainder modulo k:

for i, v in enumerate(nums):
    nums[i] = v % k

This is valid because only the remainder matters for the cost calculation. Working with reduced values keeps every element in the range [0, k), which aligns them with the candidate targets x and y.

Step 2: Enumerate all distinct target pairs.

We loop over every possible x and y in [0, k), skipping the case where x == y to honor the distinct requirement:

for x in range(k):
    for y in range(k):
        if x != y:
            ...

This produces at most k * k candidate pairs.

Step 3: Compute the cost for a fixed pair.

For each pair (x, y), we walk through the array. An element at an even index i should become x, and an element at an odd index should become y:

target = x if i % 2 == 0 else y

The cost to move a remainder v to target on a cycle of size k is the smaller of moving forward or wrapping around:

diff = abs(target - v)
cnt += min(diff, k - diff)

We sum these per-element costs into cnt.

Step 4: Track the minimum.

After summing the cost for a pair, we update the running answer:

ans = min(ans, cnt)

ans starts at inf so the first valid pair always replaces it. Once all pairs are processed, ans holds the minimum number of operations.

Complexity Analysis

Time complexity: O(k^2 * n), where n is the length of nums. There are O(k^2) distinct pairs, and for each pair we scan all n elements.
Space complexity: O(1). We modify nums in place and use only a few scalar variables.

The pattern here is straightforward brute-force enumeration: because the search space for (x, y) is bounded by k, exhaustively trying every combination is feasible and guarantees the optimal result.

Example Walkthrough

Let's trace through a concrete example to see how the enumeration approach finds the optimal answer.

Input: nums = [5, 2, 7], k = 4

Step 1: Normalize the array.

We replace each element with its remainder modulo k = 4:

5 % 4 = 1
2 % 4 = 2
7 % 4 = 3

So the normalized array becomes nums = [1, 2, 3].

The indices break down as:

Even indices (0, 2): values 1 and 3 → these must all become target x
Odd index (1): value 2 → this must become target y

Step 2 & 3: Enumerate distinct pairs (x, y) and compute costs.

Since k = 4, both x and y range over {0, 1, 2, 3}, and we skip any pair where x == y. The per-element cost from remainder v to target is min(abs(target - v), k - abs(target - v)).

Let's compute a few representative pairs:

Pair (x=1, y=2):

Index 0 (even, v=1) → target 1: min(|1-1|, 4-0) = 0
Index 1 (odd, v=2) → target 2: min(|2-2|, 4-0) = 0
Index 2 (even, v=3) → target 1: diff = |1-3| = 2, min(2, 4-2) = 2
Total = 0 + 0 + 2 = 2

Pair (x=3, y=2):

Index 0 (even, v=1) → target 3: diff = 2, min(2, 2) = 2
Index 1 (odd, v=2) → target 2: 0
Index 2 (even, v=3) → target 3: 0
Total = 2 + 0 + 0 = 2

Pair (x=2, y=2): skipped because x == y (violates the distinct requirement).

Pair (x=2, y=0):

Index 0 (even, v=1) → target 2: min(1, 3) = 1
Index 1 (odd, v=2) → target 0: diff = 2, min(2, 2) = 2
Index 2 (even, v=3) → target 2: min(1, 3) = 1
Total = 1 + 2 + 1 = 4

Step 4: Track the minimum.

As we sweep all 12 valid pairs (4 × 4 = 16 total, minus 4 where x == y), the running minimum settles on the best result. Pairs like (1, 2) and (3, 2) both achieve a cost of 2, and no pair does better.

Output: 2

Why this works: Notice the wrap-around logic in action at index 0 for pair (3, 2). The naive distance from remainder 1 to 3 is 2 going forward, but wrapping the other way (1 → 0 → 3) is also 2, so either direction costs the same here. In cases where k is larger, the wrap-around term k - diff frequently beats the direct diff, which is exactly why we take the minimum of the two. By fixing x and y up front, each element's cost becomes independent, and brute-forcing all k² distinct pairs guarantees we land on the global optimum.

Solution Implementation

1from math import inf
2
3
4class Solution:
5    def minOperations(self, nums: list[int], k: int) -> int:
6        # Reduce every number to its remainder modulo k.
7        # Each operation can increment or decrement a value by 1 (cyclically),
8        # so only the residue matters for computing the cost.
9        for i, value in enumerate(nums):
10            nums[i] = value % k
11
12        ans = inf
13
14        # Try every pair of target residues (x, y) for even/odd indices.
15        # The final array should alternate between residue x (even positions)
16        # and residue y (odd positions), with x != y.
17        for x in range(k):
18            for y in range(k):
19                if x != y:
20                    total_cost = 0
21                    for i, value in enumerate(nums):
22                        # Pick the target residue based on the index parity.
23                        target = x if i % 2 == 0 else y
24
25                        # Cost to convert `value` into `target` residue.
26                        # We can go either direction around the cycle of size k,
27                        # so take the cheaper of the two distances.
28                        diff = abs(target - value)
29                        total_cost += min(diff, k - diff)
30
31                    ans = min(ans, total_cost)
32
33        return ans
34

1class Solution {
2    /**
3     * Finds the minimum number of operations required so that the array
4     * alternates between two residue values (x at even indices, y at odd
5     * indices) under modulo k arithmetic. Each operation increments or
6     * decrements an element by 1, and values wrap around modulo k.
7     *
8     * @param nums the input array
9     * @param k    the modulus value
10     * @return the minimum total number of operations
11     */
12    public int minOperations(int[] nums, int k) {
13        int n = nums.length;
14
15        // Reduce every element to its residue modulo k.
16        for (int i = 0; i < n; i++) {
17            nums[i] %= k;
18        }
19
20        int ans = Integer.MAX_VALUE;
21
22        // Try every distinct pair (x, y) of target residues:
23        // x is the target for even indices, y for odd indices.
24        for (int x = 0; x < k; x++) {
25            for (int y = 0; y < k; y++) {
26                if (x != y) {
27                    int cnt = 0;
28
29                    // Accumulate the cost to convert each element to its target.
30                    for (int i = 0; i < n; i++) {
31                        // Even indices target x, odd indices target y.
32                        int target = (i & 1) == 0 ? x : y;
33
34                        // Direct distance between current value and target.
35                        int diff = Math.abs(target - nums[i]);
36
37                        // Because of modular wrap-around, the cost is the smaller
38                        // of moving directly or wrapping around (k - diff).
39                        cnt += Math.min(diff, k - diff);
40                    }
41
42                    // Keep track of the minimum cost across all pairs.
43                    ans = Math.min(ans, cnt);
44                }
45            }
46        }
47
48        return ans;
49    }
50}
51

1class Solution {
2public:
3    int minOperations(vector<int>& nums, int k) {
4        int n = nums.size();
5
6        // Reduce every element to its remainder modulo k,
7        // since operations are effectively performed in modulo-k space.
8        for (int& value : nums) {
9            value %= k;
10        }
11
12        int answer = INT_MAX;
13
14        // Enumerate the target remainder for even indices (x)
15        // and the target remainder for odd indices (y).
16        for (int x = 0; x < k; ++x) {
17            for (int y = 0; y < k; ++y) {
18                // The two targets must be different.
19                if (x != y) {
20                    int count = 0;
21
22                    // Accumulate the cost of converting each element
23                    // to its corresponding target based on parity of index.
24                    for (int i = 0; i < n; ++i) {
25                        int target = (i & 1) ? y : x;
26                        int diff = abs(target - nums[i]);
27                        // Choose the cheaper direction around the modulo ring.
28                        count += min(diff, k - diff);
29                    }
30
31                    answer = min(answer, count);
32                }
33            }
34        }
35
36        return answer;
37    }
38};
39

1/**
2 * Computes the minimum number of operations needed.
3 *
4 * Each element is first reduced modulo k. We then try to make all elements
5 * at even indices equal to some value x and all elements at odd indices
6 * equal to some value y (with x !== y), choosing the x and y that minimize
7 * the total cost. The cost to change a value to a target is measured as the
8 * minimal circular distance modulo k.
9 *
10 * @param nums - The input array of numbers.
11 * @param k - The modulus used for reducing values and measuring circular distance.
12 * @returns The minimum total cost over all valid (x, y) choices.
13 */
14function minOperations(nums: number[], k: number): number {
15    const n: number = nums.length;
16
17    // Reduce every element modulo k so all values fall in the range [0, k).
18    for (let i = 0; i < n; ++i) {
19        nums[i] %= k;
20    }
21
22    // Track the minimum cost found so far.
23    let answer: number = Infinity;
24
25    // Try every pair of distinct target values:
26    // x for even indices, y for odd indices.
27    for (let x = 0; x < k; ++x) {
28        for (let y = 0; y < k; ++y) {
29            if (x !== y) {
30                // Accumulated cost for the current (x, y) assignment.
31                let count: number = 0;
32
33                for (let i = 0; i < n; ++i) {
34                    // Choose the target based on the index parity.
35                    const target: number = (i & 1) === 0 ? x : y;
36
37                    // Direct absolute difference between target and current value.
38                    const diff: number = Math.abs(target - nums[i]);
39
40                    // The circular distance is the smaller of the two directions.
41                    count += Math.min(diff, k - diff);
42                }
43
44                // Update the global minimum cost.
45                answer = Math.min(answer, count);
46            }
47        }
48    }
49
50    return answer;
51}
52

Time and Space Complexity

Time Complexity: O(n × k²), where n is the length of the array nums and k is the given modulus value.

The analysis is as follows:

The first loop normalizes each element by taking the modulo, which takes O(n) time.
The main computation consists of two nested loops over x and y, each ranging from 0 to k-1, contributing O(k²) iterations.
For each valid pair (x, y) where x != y, an inner loop traverses all n elements of nums to compute the cost cnt, taking O(n) time.
Combining these, the dominant term is the triple nesting: O(k × k × n) = O(n × k²).

Space Complexity: O(1).

The analysis is as follows:

The normalization is performed in place on the input array nums, so no extra array is allocated.
Only a constant number of auxiliary variables (ans, x, y, cnt, target, diff, etc.) are used, independent of the input size.
Therefore, the additional space required is constant, giving O(1).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting the `x != y` distinctness constraint

A very common mistake is to independently optimize the even-index cost and the odd-index cost, then simply add them together. This ignores the requirement that x and y must be distinct.

# WRONG: optimizes even and odd groups independently
best_even = min(sum(min(abs(x - v), k - abs(x - v)) for v in evens) for x in range(k))
best_odd  = min(sum(min(abs(y - v), k - abs(y - v)) for v in odds)  for y in range(k))
return best_even + best_odd   # x and y might end up equal!

If the optimal x for even indices equals the optimal y for odd indices, this returns an invalid (too small) answer.

Solution: Either enumerate pairs explicitly while skipping x == y (as the brute-force code does), or use the "best + second-best" technique: compute the cheapest and second-cheapest residue cost for each group separately, then combine so that the two chosen residues differ.

def cheapest_two(values, k):
    # cost[r] = total cost to push all `values` to residue r
    cost = []
    for r in range(k):
        cost.append(sum(min(abs(r - v), k - abs(r - v)) for v in values))
    # sort residue indices by cost; keep the two smallest
    order = sorted(range(k), key=lambda r: cost[r])
    return cost, order

ec, eo = cheapest_two(evens, k)   # even group
oc, oo = cheapest_two(odds, k)    # odd group

# Best even residue and best odd residue, ensuring they differ.
if eo[0] != oo[0]:
    ans = ec[eo[0]] + oc[oo[0]]
else:
    # They collide on the cheapest choice; swap one to its 2nd best.
    ans = min(ec[eo[0]] + oc[oo[1]], ec[eo[1]] + oc[oo[0]])

This reduces the time complexity from O(k^2 * n) to O(k * n), which matters when k is large.

Pitfall 2: Mishandling the wrap-around (cyclic) distance

Because increasing or decreasing past a multiple of k wraps the remainder around, the cost between residues v and target is not simply abs(target - v). Forgetting the wrap-around branch overcounts.

# WRONG: ignores the cyclic nature
total_cost += abs(target - value)

# CORRECT: take the shorter arc on the cycle of size k
diff = abs(target - value)
total_cost += min(diff, k - diff)

For example, with k = 10, moving from residue 9 to residue 0 costs 1 (wrap forward), not 9. The min(diff, k - diff) formulation captures both directions correctly.

Pitfall 3: Not normalizing the input first

If you forget to reduce each element modulo k, the term k - diff can become negative, and min(diff, k - diff) will silently produce a wrong (negative) cost.

# Make sure every value is in [0, k) before computing costs
nums[i] = value % k

Always normalize so that both value and target lie in [0, k), guaranteeing 0 <= diff <= k and a non-negative cyclic distance.

Pitfall 4: Edge case when `k == 1`

When k == 1, the only available residue is 0, making it impossible to pick two distinct residues x != y. The brute-force loops produce no valid pair and ans stays at inf. Confirm with the problem constraints whether k >= 2 is guaranteed; if not, handle k == 1 explicitly rather than returning inf.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: