1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
/// 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]")));
}
}
|
