Prime Subtraction Operation

2601。素数減算演算

難易度: 中

トピック: 配列、数学、二分探索、貪欲、整数論

長さ n の 0 インデックス付き 整数配列 nums が与えられます。

次の操作は何度でも実行できます:

• これまでに選択したことのないインデックス i を選択し、厳密に nums[i] より小さい素数 p を選択し、nums[i] から p を減算します。

上記の操作を使用して nums を厳密に増加する配列にできる場合は true を返し、それ以外の場合は falseを返します。

厳密に増加する配列は、各要素がその前の要素より厳密に大きい配列です。

例 1:

• 入力: 数値 = [4,9,6,10]
• 出力: true
• 説明: 最初の操作: i = 0 および p = 3 を選択し、nums[0] から 3 を引くと、nums は [1,9,6,10] になります。
  • 2 番目の演算: i = 1、p = 7 では、nums[1] から 7 を減算し、nums は [1,2,6,10] と等しくなります。
  • 2 番目の操作の後、nums は厳密に昇順にソートされるため、答えは true になります。

例 2:

• 入力: 数値 = [6,8,11,12]
• 出力: true
• 説明: 当初、nums は厳密に昇順にソートされるため、操作を行う必要はありません。

例 3:

• 入力: 数値 = [5,8,3]
• 出力: false
• 説明: 数値を厳密に昇順にソートする操作を実行する方法がないことが証明できるため、答えは false です。

制約:

• 1
• 1
• nums.length == n

ヒント:

1. nums[i] から減算する素数がたくさんあるかどうかを考えてみましょう。どの素数がより最適ですか?
2. nums[i] から減算するのに最も最適な素数は、nums[i] を可能な限り小さくし、nums[i-1] より大きくする素数です。

解決策:

アルゴリズムを分解し、PHP の構文と機能に適応させる必要があります。この解決策には主に次の手順が含まれます:

1. Generating Primes (Sieve of Eratosthenes): Generate a list of all primes up to the maximum possible value in nums (1000).
2. Prime Subtraction Operation: For each number in nums, check if we can subtract a prime to make the array strictly increasing.
3. Binary Search for Prime: Use a binary search to find the largest prime less than the current number that would still keep the sequence strictly increasing.

Let's implement this solution in PHP: 2601. Prime Subtraction Operation

<?php
class Solution {

    /**
     * @param Integer[] $nums
     * @return Boolean
     */
    function primeSubOperation($nums) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Helper function to generate all primes up to n using Sieve of Eratosthenes
     *
     * @param $n
     * @return array
     */
    private function sieveEratosthenes($n) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Helper function to find the largest prime less than a given limit using binary search
     *
     * @param $primes
     * @param $limit
     * @return mixed|null
     */
    private function findLargestPrimeLessThan($primes, $limit) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Example usage:
$solution = new Solution();
echo $solution->primeSubOperation([4, 9, 6, 10]) ? 'true' : 'false';  // Output: true
echo $solution->primeSubOperation([6, 8, 11, 12]) ? 'true' : 'false'; // Output: true
echo $solution->primeSubOperation([5, 8, 3]) ? 'true' : 'false';      // Output: false
?>

Explanation:

1. primeSubOperation: Loops through each element in nums and checks if we can make each element greater than the previous one by subtracting an appropriate prime.

   • We use $this->findLargestPrimeLessThan to find the largest prime less than num - prevNum.
   • If such a prime exists, we subtract it from the current num.
   • If after subtracting the prime, the current num is not greater than prevNum, we return false.
   • Otherwise, we update prevNum to the current num.

2. sieveEratosthenes: Generates all primes up to 1000 using the Sieve of Eratosthenes and returns them as an array.

3. findLargestPrimeLessThan: Uses binary search to find the largest prime less than a given limit, ensuring we find the optimal prime for subtraction.

Complexity Analysis

• Time Complexity: O(n . √m), where n is the length of nums and m is the maximum value of an element in nums (here m = 1000).
• Space Complexity: O(m), used to store the list of primes up to 1000.

This solution will return true or false based on whether it is possible to make nums strictly increasing by performing the described prime subtraction operations.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub

The above is the detailed content of Prime Subtraction Operation. For more information, please follow other related articles on the PHP Chinese website!