LeetCode Ts-2683. Neighboring Bitwise XOR

    AllenLi
    CodingLeetCode Js-Array

    A 0-indexed array derived with length n is derived by computing the bitwise XOR (⊕) of adjacent values in a binary array original of length n.
    Specifically, for each index i in the range [0, n – 1]:
    If i = n – 1, then derived[i] = original[i] ⊕ original[0].
    Otherwise, derived[i] = original[i] ⊕ original[i + 1].
    Given an array derived, your task is to determine whether there exists a valid binary array original that could have formed derived.
    Return true if such an array exists or false otherwise.
    A binary array is an array containing only 0’s and 1’s

    一個長度為 n、從 0-indexed 開始的陣列 derived，透過長度為 n 的二元陣列 original 中相鄰的值做 XOR 運算。
具體來說，對於每個 index i (範圍從 0  到 n - 1)：
如果 i 是 n - 1，那麼 derived[i] = original[i] ⊕ original[0].
否則，derived[i] = original[i] ⊕ original[i + 1].
給你一個陣列 derived，你需要判斷是否存在一個合法的二元 original 陣列，可以產生出這個 derived。
如果存在就回傳 true，否則回傳 false。
二元陣列指的是裡面只有 0 和 1 的陣列。

    Example 1:

    Input: derived = [1,1,0]
Output: true
Explanation: A valid original array that gives derived is [0,1,0].
derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1 
derived[1] = original[1] ⊕ original[2] = 1 ⊕ 0 = 1
derived[2] = original[2] ⊕ original[0] = 0 ⊕ 0 = 0

    Example 2:

    Input: derived = [1,1]
Output: true
Explanation: A valid original array that gives derived is [0,1].
derived[0] = original[0] ⊕ original[1] = 1
derived[1] = original[1] ⊕ original[0] = 1

    Example 3:

    Input: derived = [1,0]
Output: false
Explanation: There is no valid original array that gives derived.

    Solution:
    根據題意，每個 derived[i] = original[i] ⊕ original[i + 1]，
    如果把所有的 derived 的值全部 XOR 起來：
    每個 original 都會被 XOR 兩次，所以互相抵銷，
    結果必須是 0 才可能成立。
    所以我們用 reduce((acc, cur) => acc ^ cur, 0) 將累積值 acc 與當前值 cur 依序做 XOR，
    最後檢查最終結果是否為 0 即可。

    Code 1: BigO(n)

    function doesValidArrayExist(derived: number[]): boolean {
    return (derived.reduce((acc, cur) => acc ^ cur, 0) === 0);
};

    FlowChart:
    Example 1

    Input: derived = [1,1,0]

Step 0: acc = 0, cur = 1, acc ^ cur = 1
Step 1: acc = 1, cur = 1, acc ^ cur = 0
Step 2: acc = 0, cur = 0, acc ^ cur = 0
Final XOR result: 0

    Example 2

    Input: derived = [1,1]

Step 0: acc = 0, cur = 1, acc ^ cur = 1
Step 1: acc = 1, cur = 1, acc ^ cur = 0
Final XOR result: 0

    Example 3

    Input: derived = [1,1]

Step 0: acc = 0, cur = 1, acc ^ cur = 1
Step 1: acc = 1, cur = 0, acc ^ cur = 1
Final XOR result: 1

    Related Posts