3192. Minimum Operations to Make Binary Array Elements Equal to One II / TypeScript

You are given a binary array nums.

You can do the following operation on the array any number of times (possibly zero):

• Choose any index i from the array and flip all the elements from index i to the end of the array.

Flipping an element means changing its value from 0 to 1, and from 1 to 0.

Return the minimum number of operations required to make all elements in nums equal to 1.

 

Example 1:

Input: nums = [0,1,1,0,1]

Output: 4

Explanation:
We can do the following operations:

• Choose the index i = 1. The resulting array will be nums = [0,0,0,1,0].
• Choose the index i = 0. The resulting array will be nums = [1,1,1,0,1].
• Choose the index i = 4. The resulting array will be nums = [1,1,1,0,0].
• Choose the index i = 3. The resulting array will be nums = [1,1,1,1,1].

Example 2:

Input: nums = [1,0,0,0]

Output: 1

Explanation:
We can do the following operation:

• Choose the index i = 1. The resulting array will be nums = [1,1,1,1].

출처 : https://leetcode.com/problems/minimum-operations-to-make-binary-array-elements-equal-to-one-ii/description/

 

풀이 

function minOperations(input: number[]): number {
    let flip = 0;
    let minOperations = 0;
    for (let i = 0; i < input.length; ++i) {
        if ((input[i] ^ flip) === 0) {
            ++minOperations;
            flip ^= 1;
        }
    }
    return minOperations;
};

 

배열이 모두 1 이 되는 최소 연산 횟수

 

• flip 변수를 0으로 초기화. (flip은 현재 플립 상태를 저장.)
• minOperations 변수를 0으로 초기화. (minOperations는 최소 연산 횟수를 저장.)
• 배열 input을 처음부터 끝까지 순회.
• 각 요소에 대해 (input[i] ^ flip) 값이 0인지 확인.
  • XOR 연산자 ^를 사용
  • input[i]와 flip의 XOR 결과가 0이면 두 값이 같다는 뜻.
• XOR 결과가 0이면, minOperations를 1 증가시키고 flip을 1로 토글.
• (flip ^= 1은 flip의 현재 값을 0에서 1로, 또는 1에서 0으로 바꿈.)
• 최종적으로 minOperations 값을 반환

 

예시

배열이 [1, 1, 0, 1, 0]인 경우

• flip이 초기값 0일 때, 첫 번째 요소 1과 flip의 XOR 값은 1 ^ 0 = 1 (0이 아님).
• 두 번째 요소 1과 flip의 XOR 값도 1 ^ 0 = 1 (0이 아님).
• 세 번째 요소 0과 flip의 XOR 값은 0 ^ 0 = 0 (0임). 따라서 연산을 실행합니다: minOperations++ 및 flip ^= 1 -> flip = 1.
• 네 번째 요소 1과 flip의 XOR 값은 1 ^ 1 = 0 (0임). 따라서 연산을 실행합니다: minOperations++ 및 flip ^= 1 -> flip = 0.
• 다섯 번째 요소 0과 flip의 XOR 값은 0 ^ 0 = 0 (0임). 따라서 연산을 실행합니다: minOperations++ 및 flip ^= 1 -> flip = 1.