主題

LeetCode - 1969. Minimum Non-Zero Product of the Array Elements 解題心得

Not In My Back Yard | 2022-01-21 00:00:01 | 巴幣 0 | 人氣 95

題目連結:


題目意譯:
你被給定一正整數 p。考慮一陣列 nums(索引值從 1 開始)其由含端點之範圍 [1, 2 ^ p - 1] 中的整數並以它們的二進位制來表示所組成。你被允許執行任意次以下操作:
從 nums 中選擇兩元素 x 、 y。
選擇 x 中一個位元並與 y 中的對應位元去交換。對應位元代表著兩整數相同位置的位元。

例如如果 x = 1101 而 y = 0011,將從右邊數來第 2 個位元交換後,我們得到 x = 1111 以及 y = 0001。

找到經由若干次上述操作後 nums 之最小可能非零之乘積值。將這個乘積模 10 ^ 9 + 7 後回傳。

注:答案於模操作執行前,應為最小乘積值。
(譯者注:即「最小」不是所有可能乘積值取餘數「後」當中的最小值而是取餘數「前」的)

限制:
1 ≦ p ≦ 60



範例測資:
範例 1:
輸入: p = 1
輸出: 1
解釋: nums = [1].
其只含一個元素,所以乘積等於該元素。

範例 2:
輸入: p = 2
輸出: 6
解釋: nums = [01, 10, 11].
任意交換只會得到乘積值 0 或是保持原樣。
因此陣列乘積 1 × 2 × 3 = 6 已經是最小的值了。

範例 3:
輸入: p = 3
輸出: 1512
解釋: nums = [001, 010, 011, 100, 101, 110, 111]
- 第一次操作中我們可以將第二以及第五元素最左側的位元交換。
    - 結果之陣列為 [001, 110, 011, 100, 001, 110, 111]。
- 第一次操作中我們可以將第三以及第四元素中間的位元交換。
    - 結果之陣列為 [001, 110, 001, 110, 001, 110, 111].
陣列乘積為 1 × 6 × 1 × 6 × 1 × 6 × 7 = 1512,其為最小可能的乘積值。


解題思維:
可以看到十進位數字 1(二進位表示法為 000……1)越多越好,然後剩下的位元盡量聚在一起。因此例如 p = 3 時,最小乘積值的 nums 應為以下形式:
001
001
001
111
110
110
110
乘積值為 1512。

又例如 p = 4 會得到
0001
0001
0001
0001
0001
0001
0001
1111
1110
1110
1110
1110
1110
1110
1110
乘積值為 1581202560。

因此我們可以看到表示法全是 1 的(即 2 ^ p - 1)只會有一個、表示法除了最右側的位元以外都是 1 的(即 2 ^ p - 2)會有 2 ^ (p - 1) - 1 個。因此最小乘積值為
而右邊的項次可以利用快速冪求得並取模 10 ^ 9 + 7,參見這題



不過我無法證明以上的正確性。希望有人可以補充說明。

目前遇到的問題是無法說明為何一定不會存在從上面「最佳」的乘積值開始交換位元之操作,數值先變大一陣子之後就變得比「最佳」還小的情況。又或是兩兩配對來交換成以上的最佳狀態,但如同前面所述無法說明不會有別的交換法使得乘積更小。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作