2300. Successful Pairs of Spells and Potions Medium

1/**
2 * [2300] Successful Pairs of Spells and Potions
3 *
4 * You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the i^th spell and potions[j] represents the strength of the j^th potion.
5 * You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.
6 * Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the i^th spell.
7 *  
8 * Example 1:
9 *
10 * Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
11 * Output: [4,0,3]
12 * Explanation:
13 * - 0^th spell: 5 * [1,2,3,4,5] = [5,<u>10</u>,<u>15</u>,<u>20</u>,<u>25</u>]. 4 pairs are successful.
14 * - 1^st spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
15 * - 2^nd spell: 3 * [1,2,3,4,5] = [3,6,<u>9</u>,<u>12</u>,<u>15</u>]. 3 pairs are successful.
16 * Thus, [4,0,3] is returned.
17 *
18 * Example 2:
19 *
20 * Input: spells = [3,1,2], potions = [8,5,8], success = 16
21 * Output: [2,0,2]
22 * Explanation:
23 * - 0^th spell: 3 * [8,5,8] = [<u>24</u>,15,<u>24</u>]. 2 pairs are successful.
24 * - 1^st spell: 1 * [8,5,8] = [8,5,8]. 0 pairs are successful.
25 * - 2^nd spell: 2 * [8,5,8] = [<u>16</u>,10,<u>16</u>]. 2 pairs are successful.
26 * Thus, [2,0,2] is returned.
27 *
28 *  
29 * Constraints:
30 *
31 * n == spells.length
32 * m == potions.length
33 * 1 <= n, m <= 10^5
34 * 1 <= spells[i], potions[i] <= 10^5
35 * 1 <= success <= 10^10
36 *
37 */
38pub struct Solution {}
39
40// problem: https://leetcode.com/problems/successful-pairs-of-spells-and-potions/
41// discuss: https://leetcode.com/problems/successful-pairs-of-spells-and-potions/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44
45impl Solution {
46    pub fn successful_pairs(spells: Vec<i32>, potions: Vec<i32>, success: i64) -> Vec<i32> {
47        let mut potions = potions.clone();
48        potions.sort();
49        let n = spells.len();
50        let m = potions.len();
51
52        let mut result = vec![0; n];
53
54        for i in 0..n {
55            let mut start = 0 as i32;
56            let mut end = m as i32;
57
58            while start < end {
59                let mid = start + (end - start) / 2;
60                if spells[i] as i64 * potions[mid as usize] as i64 >= success {
61                    end = mid;
62                } else {
63                    start = mid + 1;
64                }
65            }
66
67            result[i] = (m as i32) - start;
68        }
69
70        result
71    }
72}
73
74// submission codes end
75
76#[cfg(test)]
77mod tests {
78    use super::*;
79
80    #[test]
81    fn test_2300() {
82        assert_eq!(
83            Solution::successful_pairs(vec![5, 1, 3], vec![1, 2, 3, 4, 5], 7),
84            vec![4, 0, 3]
85        );
86    }
87}
88