Operasi Tolak Perdana

2601. Operasi Tolak Perdana

Kesukaran: Sederhana

Topik: Tatasusunan, Matematik, Carian Binari, Tamak, Teori Nombor

Anda diberi 0-diindeks nombor tatasusunan integer dengan panjang n.

Anda boleh melakukan operasi berikut seberapa banyak kali yang anda mahu:

• Pilih indeks i yang belum anda pilih sebelum ini, dan pilih p utama kurang daripada nombor[i], kemudian tolak p daripada nombor[i].

Kembali benar jika anda boleh menjadikan nombor tatasusunan yang semakin meningkat menggunakan operasi di atas dan palsu sebaliknya.

A tatasusunan yang semakin meningkat ialah tatasusunan yang setiap elemennya lebih besar daripada elemen sebelumnya.

Contoh 1:

• Input: nombor = [4,9,6,10]
• Output: benar
• Penjelasan: Dalam operasi pertama: Pilih i = 0 dan p = 3, dan kemudian tolak 3 daripada nombor[0], supaya nombor menjadi [1,9,6,10].
  • Dalam operasi kedua: i = 1, p = 7, tolak 7 daripada nombor[1], jadi nombor menjadi sama dengan [1,2,6,10].
  • Selepas operasi kedua, nombor diisih mengikut susunan yang semakin meningkat, jadi jawapannya adalah benar.

Contoh 2:

• Input: nombor = [6,8,11,12]
• Output: benar
• Penjelasan: Pada mulanya nombor diisih mengikut susunan yang semakin meningkat, jadi kami tidak perlu membuat sebarang operasi.

Contoh 3:

• Input: nombor = [5,8,3]
• Output: palsu
• Penjelasan: Dapat dibuktikan bahawa tiada cara untuk melakukan operasi untuk membuat nombor disusun mengikut susunan yang semakin meningkat, jadi jawapannya adalah palsu.

Kekangan:

• 1 <= nums.length <= 1000
• 1 <= angka[i] <= 1000
• bilangan panjang == n

Petunjuk:

1. Fikirkan jika kita mempunyai banyak nombor perdana untuk ditolak daripada nombor[i]. Perdana mana yang lebih optimum?
2. Nombor perdana yang paling optimum untuk ditolak daripada nombor[i] ialah yang menjadikan nombor[i] terkecil mungkin dan lebih besar daripada nombor[i-1].

Penyelesaian:

Kita perlu memecahkan algoritma dan menyesuaikannya dengan sintaks dan fungsi PHP. Penyelesaian terutamanya melibatkan langkah-langkah berikut:

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

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:




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.


sieveEratosthenes: Generates all primes up to 1000 using the Sieve of Eratosthenes and returns them as an array.
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



          

            
  

            
        
Atas ialah kandungan terperinci Operasi Tolak Perdana. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!