/// 2601. Prime Subtraction Operation (Medium)
///
/// You are given a *0-indexed* integer array nums of length n.
///
/// You can perform the following operation as many times as you want:
///
///   * Pick an index i that you haven’t picked before, and pick a prime p
///   *strictly less than* nums[i], then subtract p from nums[i].
///
/// Return true if you can make nums a strictly increasing array using the above
/// operation and false otherwise.
///
/// A *strictly increasing array* is an array whose each element is strictly
/// greater than its preceding element.
///
/// *Example 1:*
///
///   *Input:* nums = [4,9,6,10]
///   *Output:* true
///   *Explanation:* In the first operation: Pick i = 0 and p = 3, and then
///   subtract 3 from nums[0], so that nums becomes [1,9,6,10].
///   In the second operation: i = 1, p = 7, subtract 7 from nums[1], so nums
///   becomes equal to [1,2,6,10].
///   After the second operation, nums is sorted in strictly increasing order, so
///   the answer is true.
///
/// *Example 2:*
///
///   *Input:* nums = [6,8,11,12]
///   *Output:* true
///   *Explanation: *Initially nums is sorted in strictly increasing order, so we
///   don't need to make any operations.
///
/// *Example 3:*
///
///   *Input:* nums = [5,8,3]
///   *Output:* false
///   *Explanation:* It can be proven that there is no way to perform operations
///   to make nums sorted in strictly increasing order, so the answer is false.
///
/// *Constraints:*
///
///   * 1 <= nums.length <= 1000
///   * 1 <= nums[i] <= 1000
///   * nums.length == n
///
use leetcode::arg_into;
use std::cmp;

struct Solution {}

impl Solution {
    pub fn prime_sub_operation(mut nums: Vec<i32>) -> bool {
        let mut primes = Vec::new();
        let mut sieve = vec![false; 1000];
        for i in 2..=1000 {
            if !sieve[i - 1] {
                for k in (i..=1000).step_by(i) {
                    sieve[k - 1] = true;
                }
                primes.push(i as i32);
            }
        }
        let mut lut = vec![primes.len(); 1000];
        let mut k = primes.len() - 1;
        for i in (1..=1000usize).rev() {
            if i as i32 <= primes[k] {
                if k > 0 && i as i32 == primes[k - 1] {
                    k -= 1;
                }
                lut[i - 1] = k;
            }
        }
        for i in (0..nums.len() - 1).rev() {
            if nums[i] >= nums[i + 1] {
                let diff = cmp::max(2, nums[i] - nums[i + 1] + 1) as usize;
                if lut[diff - 1] >= primes.len() || primes[lut[diff - 1]] >= nums[i] {
                    return false;
                }
                nums[i] -= primes[lut[diff - 1]];
            }
        }
        true
    }
}

fn main() {
    println!("{:?}", Solution::prime_sub_operation(arg_into(1)));
}

#[cfg(test)]
mod tests {
    use crate::Solution;
    use leetcode::vi;

    #[test]
    fn test() {
        assert!(Solution::prime_sub_operation(vi("[4,9,6,10]")));
        assert!(Solution::prime_sub_operation(vi("[6,8,11,12]")));
        assert!(!Solution::prime_sub_operation(vi("[5,8,3]")));
        assert!(Solution::prime_sub_operation(vi("[998,2]")));
    }
}