https://leetcode.com/problems/prime-subtraction-operation
2601. Prime Subtraction Operation
給一個長度為 n 的 0 索引整數數組 nums
可以做任意次數以下的操作
選一個沒選過的索引 i 選擇嚴格小於 nums[i] 的質數 p 然後 nums[i] - p
回傳 true 當做完上面的操作後能使 nums 是嚴格遞增的數組 否則回傳 false
嚴格遞增數組 指每個元素都嚴格大於前一個元素的數組
Example 1:
Input: nums = [4,9,6,10]
Output: true
Explanation:
i = 0, p = 3 => [1,9,6,10]
i = 1, p = 7 => [1,2,6,10]
Example 2:
Input: nums = [6,8,11,12]
Output: true
Explanation: 已嚴格遞增
Example 3:
Input: nums = [5,8,3]
Output: false
Explanation: 無解
Constraints:
1 <= nums.length <= 1000
1 <= nums[i] <= 1000
nums.length == n
思路：
就是每個位置只能減一次 又要嚴格遞增 所以從最後一個開始處理
先做出 1000 以內的所有質數 判斷質數從小到大哪個能使兩數變遞增
如果無法變成遞增就直接回傳 False
Python Code:
class Solution:
def primeSubOperation(self, nums: List[int]) -> bool:
primes = (2, 3, 5, 7, ..., 971, 977, 983, 991, 997) # 太多就不列出了
n = len(nums) - 1
while n:
num = nums[n-1]
if num < nums[n]: # 已嚴格遞增
n -= 1
continue
for p in primes:
if num <= p:
return False # 因為要求 p < num 找不到代表無法達成
if num - p < nums[n]:
nums[n-1] = num - p
n -= 1
break
else:
return False # 在沒有 break 的情況下 一樣代表無法遞增
return True # 跑完代表嚴格遞增完成