What is the optimal approach to solving the Prime Subtraction Operation problem?

The optimal approach involves using binary search to efficiently select the largest valid prime to subtract from each element in the array.

How does binary search improve the solution for the Prime Subtraction Operation problem?

Binary search allows you to quickly find the largest prime smaller than or equal to each element, minimizing unnecessary operations and ensuring efficiency.

Can this problem be solved with a greedy algorithm?

Yes, a greedy algorithm is a key component of the solution, as you always want to subtract the largest possible prime at each step to make the array strictly increasing.

What is the time complexity of the Prime Subtraction Operation problem?

The time complexity is O(n + m \log \log (m)) where n is the length of the array and m is the range of values in nums.

Are there any common mistakes to avoid when solving the Prime Subtraction Operation problem?

Common mistakes include failing to select the correct prime at each index, inefficient prime searching, and misunderstanding the problem's greedy nature.

#2601

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

质数减法运算

给你一个下标从 0 开始的整数数组 nums ，数组长度为 n 。你可以执行无限次下述运算：选择一个之前未选过的下标 i ，并选择一个严格小于 nums[i] 的质数 p ，从 nums[i] 中减去 p 。如果你能通过上述运算使得 nums 成为严格递增数组，则返回 true ；否则返回 …

数组数学二分查找贪心数论

题目描述

给你一个下标从 0 开始的整数数组 nums ，数组长度为 n 。

你可以执行无限次下述运算：

选择一个之前未选过的下标 i ，并选择一个 严格小于 nums[i] 的质数 p ，从 nums[i] 中减去 p 。

如果你能通过上述运算使得 nums 成为严格递增数组，则返回 true ；否则返回 false 。

严格递增数组 中的每个元素都严格大于其前面的元素。

示例 1：

输入：nums = [4,9,6,10]
输出：true
解释：
在第一次运算中：选择 i = 0 和 p = 3 ，然后从 nums[0] 减去 3 ，nums 变为 [1,9,6,10] 。
在第二次运算中：选择 i = 1 和 p = 7 ，然后从 nums[1] 减去 7 ，nums 变为 [1,2,6,10] 。
第二次运算后，nums 按严格递增顺序排序，因此答案为 true 。

示例 2：

输入：nums = [6,8,11,12]
输出：true
解释：nums 从一开始就按严格递增顺序排序，因此不需要执行任何运算。

示例 3：

输入：nums = [5,8,3]
输出：false
解释：可以证明，执行运算无法使 nums 按严格递增顺序排序，因此答案是 false 。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 1000
nums.length == n

lightbulb

解题思路

方法一：预处理质数 + 二分查找

我们先预处理得到 $1000$ 以内的所有质数，记录在数组 $p$ 中。

对于数组 $nums$ 中的每个元素 $nums[i]$ ，我们需要找到一个质数 $p[j]$ ，使得 p[j] \gt nums[i] - nums[i + 1]，并且 $p[j]$ 尽可能小。如果找不到这样的质数，说明无法通过减法运算使得 $nums$ 严格递增，返回 false。如果找到了这样的质数，我们就将 $nums[i]$ 减去 $p[j]$ ，并继续处理下一个元素。

如果 $nums$ 中的所有元素都处理完了，说明可以通过减法运算使得 $nums$ 严格递增，返回 true。

时间复杂度 $O(n \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        p = []
        for i in range(2, max(nums)):
            for j in p:
                if i % j == 0:
                    break
            else:
                p.append(i)

        n = len(nums)
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                continue
            j = bisect_right(p, nums[i] - nums[i + 1])
            if j == len(p) or p[j] >= nums[i]:
                return False
            nums[i] -= p[j]
        return True

speed

复杂度分析

指标	值
时间	O(n + m \log \log (m))
空间	O(m)

psychology

面试官常问的追问

外企场景

question_mark
Assess the candidate's understanding of prime number properties.
question_mark
Look for knowledge in binary search optimization.
question_mark
Check if the candidate is comfortable using greedy algorithms.

warning

常见陷阱

外企场景

error
Forgetting to subtract the correct prime at each index.
error
Not applying binary search efficiently, leading to unnecessary computation.
error
Confusing prime subtraction with other array manipulation techniques.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Adjust the problem by limiting the available primes to smaller sets.
arrow_right_alt
Alter the array length to test scalability and performance.
arrow_right_alt
Change the problem to require the array to be non-decreasing instead of strictly increasing.

help

常见问题

外企场景

继续练习

#3605 数组的最小稳定性因子 #2607 使子数组元素和相等 #2790 长度递增组的最大数目