Skip to content

3937. Minimum Operations to Make Array Modulo Alternating I

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 (0 <= x, y < k) such that:

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

Return the minimum number of operations required to make nums modulo alternating.

Β 

Example 1:

Input: nums = [1,4,2,8], k = 3

Output: 2

Explanation:

  • Let's choose x = 1 for even indices and y = 2 for odd indices.
  • Perform the following operations:
    • Increment nums[1] = 4 by 1, giving nums = [1, 5, 2, 8].
    • Decrement nums[2] = 2 by 1, giving nums = [1, 5, 1, 8].
  • Now, for even indices, nums[i] % k = 1, and for odd indices, nums[i] % k = 2.
  • Thus, the total number of operations required is 2.

Example 2:

Input: nums = [1,1,1], k = 3

Output: 1

Explanation:

  • Incrementing nums[1] by 1 gives nums = [1, 2, 1], which satisfies the condition with x = 1 and y = 2.
  • Thus, the total number of operations required is 1.

Β 

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 109
  • 2 <= k <= 100

Solutions

Solution 1: Enumeration

We can enumerate the target value \(x\) for even indices and the target value \(y\) for odd indices, where \(0 \leq x, y < k\) and \(x \neq y\). For each element, we calculate the number of operations required to change it to the target value, and accumulate the total number of operations. Finally, we return the minimum value among all enumeration results.

The time complexity is \(O(n \times k^2)\), where \(n\) is the length of the array \(\textit{nums}\). The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def minOperations(self, nums: list[int], k: int) -> int:
        for i, v in enumerate(nums):
            nums[i] = v % k
        ans = inf
        for x in range(k):
            for y in range(k):
                if x != y:
                    cnt = 0
                    for i, v in enumerate(nums):
                        target = x if i % 2 == 0 else y
                        diff = abs(target - v)
                        cnt += min(diff, k - diff)
                    ans = min(ans, cnt)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int minOperations(int[] nums, int k) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            nums[i] %= k;
        }

        int ans = Integer.MAX_VALUE;

        for (int x = 0; x < k; ++x) {
            for (int y = 0; y < k; ++y) {
                if (x != y) {
                    int cnt = 0;

                    for (int i = 0; i < n; ++i) {
                        int target = (i & 1) == 0 ? x : y;
                        int diff = Math.abs(target - nums[i]);
                        cnt += Math.min(diff, k - diff);
                    }

                    ans = Math.min(ans, cnt);
                }
            }
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int n = nums.size();

        for (int& v : nums) {
            v %= k;
        }

        int ans = INT_MAX;

        for (int x = 0; x < k; ++x) {
            for (int y = 0; y < k; ++y) {
                if (x != y) {
                    int cnt = 0;

                    for (int i = 0; i < n; ++i) {
                        int target = (i & 1) ? y : x;
                        int diff = abs(target - nums[i]);
                        cnt += min(diff, k - diff);
                    }

                    ans = min(ans, cnt);
                }
            }
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func minOperations(nums []int, k int) int {
    for i, v := range nums {
        nums[i] = v % k
    }

    ans := int(^uint(0) >> 1)

    for x := 0; x < k; x++ {
        for y := 0; y < k; y++ {
            if x != y {
                cnt := 0

                for i, v := range nums {
                    target := x
                    if i&1 == 1 {
                        target = y
                    }

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

                ans = min(ans, cnt)
            }
        }
    }

    return ans
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function minOperations(nums: number[], k: number): number {
    const n = nums.length;

    for (let i = 0; i < n; ++i) {
        nums[i] %= k;
    }

    let ans = Infinity;

    for (let x = 0; x < k; ++x) {
        for (let y = 0; y < k; ++y) {
            if (x !== y) {
                let cnt = 0;

                for (let i = 0; i < n; ++i) {
                    const target = (i & 1) === 0 ? x : y;
                    const diff = Math.abs(target - nums[i]);
                    cnt += Math.min(diff, k - diff);
                }

                ans = Math.min(ans, cnt);
            }
        }
    }

    return ans;
}

Comments