leetcode

Leetcode problem solutions
git clone https://git.sinitax.com/sinitax/leetcode
Log | Files | Refs | sfeed.txt

2601-prime-subtraction-operation.rs (3193B)

      1/// 2601. Prime Subtraction Operation (Medium)
      2///
      3/// You are given a *0-indexed* integer array nums of length n.
      4///
      5/// You can perform the following operation as many times as you want:
      6///
      7///   * Pick an index i that you haven’t picked before, and pick a prime p
      8///   *strictly less than* nums[i], then subtract p from nums[i].
      9///
     10/// Return true if you can make nums a strictly increasing array using the above
     11/// operation and false otherwise.
     12///
     13/// A *strictly increasing array* is an array whose each element is strictly
     14/// greater than its preceding element.
     15///
     16/// *Example 1:*
     17///
     18///   *Input:* nums = [4,9,6,10]
     19///   *Output:* true
     20///   *Explanation:* In the first operation: Pick i = 0 and p = 3, and then
     21///   subtract 3 from nums[0], so that nums becomes [1,9,6,10].
     22///   In the second operation: i = 1, p = 7, subtract 7 from nums[1], so nums
     23///   becomes equal to [1,2,6,10].
     24///   After the second operation, nums is sorted in strictly increasing order, so
     25///   the answer is true.
     26///
     27/// *Example 2:*
     28///
     29///   *Input:* nums = [6,8,11,12]
     30///   *Output:* true
     31///   *Explanation: *Initially nums is sorted in strictly increasing order, so we
     32///   don't need to make any operations.
     33///
     34/// *Example 3:*
     35///
     36///   *Input:* nums = [5,8,3]
     37///   *Output:* false
     38///   *Explanation:* It can be proven that there is no way to perform operations
     39///   to make nums sorted in strictly increasing order, so the answer is false.
     40///
     41/// *Constraints:*
     42///
     43///   * 1 <= nums.length <= 1000
     44///   * 1 <= nums[i] <= 1000
     45///   * nums.length == n
     46///
     47use leetcode::arg_into;
     48use std::cmp;
     49
     50struct Solution {}
     51
     52impl Solution {
     53    pub fn prime_sub_operation(mut nums: Vec<i32>) -> bool {
     54        let mut primes = Vec::new();
     55        let mut sieve = vec![false; 1000];
     56        for i in 2..=1000 {
     57            if !sieve[i - 1] {
     58                for k in (i..=1000).step_by(i) {
     59                    sieve[k - 1] = true;
     60                }
     61                primes.push(i as i32);
     62            }
     63        }
     64        let mut lut = vec![primes.len(); 1000];
     65        let mut k = primes.len() - 1;
     66        for i in (1..=1000usize).rev() {
     67            if i as i32 <= primes[k] {
     68                if k > 0 && i as i32 == primes[k - 1] {
     69                    k -= 1;
     70                }
     71                lut[i - 1] = k;
     72            }
     73        }
     74        for i in (0..nums.len() - 1).rev() {
     75            if nums[i] >= nums[i + 1] {
     76                let diff = cmp::max(2, nums[i] - nums[i + 1] + 1) as usize;
     77                if lut[diff - 1] >= primes.len() || primes[lut[diff - 1]] >= nums[i] {
     78                    return false;
     79                }
     80                nums[i] -= primes[lut[diff - 1]];
     81            }
     82        }
     83        true
     84    }
     85}
     86
     87fn main() {
     88    println!("{:?}", Solution::prime_sub_operation(arg_into(1)));
     89}
     90
     91#[cfg(test)]
     92mod tests {
     93    use crate::Solution;
     94    use leetcode::vi;
     95
     96    #[test]
     97    fn test() {
     98        assert!(Solution::prime_sub_operation(vi("[4,9,6,10]")));
     99        assert!(Solution::prime_sub_operation(vi("[6,8,11,12]")));
    100        assert!(!Solution::prime_sub_operation(vi("[5,8,3]")));
    101        assert!(Solution::prime_sub_operation(vi("[998,2]")));
    102    }
    103}