題目連結:
題目意譯:
給定三個正整數 a 、 b 和 c。回傳最小所需的翻轉 a 和 b 中若干個位元的次數,使得 (a OR b == c)(按位元之 OR 操作)。
一個翻轉操作是由改變一個二進位表示法中的單一位元從 1 變成 0 或是從 0 變成 1 而組成。
限制:
1 ≦ a ≦ 10 ^ 9
1 ≦ b ≦ 10 ^ 9
1 ≦ c ≦ 10 ^ 9
範例測資:
範例 1:
輸入: a = 2, b = 6, c = 5
輸出: 3
解釋: 經過翻轉後,a = 1 、 b = 4 、 c = 5 使得 (a OR b == c)。
範例 2:
輸入: a = 4, b = 2, c = 7
輸出: 1
範例 3:
輸入: a = 1, b = 2, c = 3
輸出: 0
解題思維:
可以看到每一個位元之間互相獨立。所以最小的所需翻轉數只需要看每一位元各自最小所需的翻轉次數即可。
假設現在看的是第 i 位元,而 a 、 b 和 c 第 i 個位元的值分別為 ai 、 bi 和 ci。此時如果 (ai OR bi) != ci,則代表著我們需要至少翻轉一次;反之,則不用任何翻轉(因為已經一樣了)。
假設現在 (ai OR bi) != ci,則我們可以把情況分類:
ai 和 bi 兩者皆為 1,則此時代表著我們需要同時翻轉 ai 和 bi 來使得 OR 之結果為 0。因此所需次數為 2;
ai 或 bi 其中一個為 1,則此時代表著我們只要把是 1 的那一個位元翻轉即可。因此所需次數為 1;
ai 和 bi 兩者皆為 0,則此時代表著我們只需要翻轉其中一者便可以使結果為 1。因此所需次數為 1。
最後把所有位元各自的所需翻轉次數加總即為所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。