🐢

LeetCode - Find The Original Array of Prefix Xor をSwiftで解説する

2022/10/09に公開

iOS

元の問題は英語なので、代わりに翻訳したものを記載しています。
回答はあくまでも例であり、他の方法も存在します。

前置き

Swiftで排他的論理和(xor)の計算をしたことない人にとっては、程よい問題かと思います。

問題

問題	難易度
Find The Original Array of Prefix Xor	medium

大きさnの整数配列prefが与えられたとき、これを満たす大きさnの配列arrを求めて返します。

pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]

^はビット単位のxor演算を表します。
答えは一意になります。

補足として、以下のようなテストケースが与えられます。

ex1
Input: pref = [5,2,0,3,1]
Output: [5,7,2,3,2]

Explanation: From the array [5,7,2,3,2] we have the following:
- pref[0] = 5.
- pref[1] = 5 ^ 7 = 2.
- pref[2] = 5 ^ 7 ^ 2 = 0.
- pref[3] = 5 ^ 7 ^ 2 ^ 3 = 3.
- pref[4] = 5 ^ 7 ^ 2 ^ 3 ^ 2 = 1.


ex2
Input: pref = [13]
Output: [13]

Explanation: 
We have pref[0] = arr[0] = 13.

答え

排他的論理和（XOR）とは

図を見てもらうのが理解しやすいと思います。

（引用：コードを短くする為の論理和と論理積（と排他的論理和）のおさらい）

簡単にいうと、XORはいずれかがtrueの場合のみ、trueの判定になるものです。
今回はこれをビット演算で使っていきます。

コンピュータはすべての情報を内部的にはビット列として表しており、CPU（MPU/マイクロプロセッサ）にはビット演算用の命令が豊富に用意されている。機械語（マシン語）のプログラムでは様々な処理に用いられる演算であり、高水準言語のプログラムに直接記述されていなくても実際の処理では内部的に多用されている。

（引用：e-words ビット演算【bitwise operation】）

ビット演算では、0と1で計算していくことになります。２進数だとイメージしやすいでしょう。

example

1100 ^ 1010 = 0110

これを10進数に変換するとこうなります。

12 ^ 10 = 6

これを元に問題を解いていきます。

解説

まずは、与えられた ex1 を例にパターンを考えていくのが良いでしょう。
配列prefは [5,2,0,3,1] で、以下のような構成になっています。

pref[0] = 5
pref[1] = 5 ^ 7 = 2
pref[2] = 5 ^ 7 ^ 2 = 0
pref[3] = 5 ^ 7 ^ 2 ^ 3 = 3
pref[4] = 5 ^ 7 ^ 2 ^ 3 ^ 2 = 1

これを変形すると、以下のようになります。

pref[0] = 5
pref[1] = pref[0] ^ 7 = 2
pref[2] = pref[1] ^ 2 = 0
pref[3] = pref[2] ^ 3 = 3
pref[4] = pref[3] ^ 2 = 1

つまり、以下のような一般項として表すことができます。

pref[n+1] = pref[n] ^ x

(※ 0 <= x <= 10^6)

今回の問題から求めたい値は、上記のxの部分です。

^は逆にかけることで逆算することができるので

x = pref[n] ^ pref[n+1]

になります。

ここまでくれば、プログラミングに変換できるでしょう。

func findArray(_ pref: [Int]) -> [Int] {
    guard 1 < pref.count else { return pref }
    
    var result = [pref[0]]
    
    for i in 0..<pref.count - 1 {
        result.append(pref[i] ^ pref[i + 1])
    }

    return result
}

０件または１件の場合は計算が必要がないので、早期でリターンしています。
２件以上ある場合は、順に値を１つずつ計算していくことで、答えを求めることができます。

実行結果

Runtime	Memory
2000ms前後	25MB前後

前置き

問題

答え

排他的論理和（XOR）とは

example

解説

実行結果

Discussion