3806. Maximum Bitwise AND After Increment Operations Hard

1/**
2 * [3806] Maximum Bitwise AND After Increment Operations
3 *
4 * You are given an integer array nums and two integers k and m.
5 * You may perform at most k operations. In one operation, you may choose any index i and increase nums[i] by 1.
6 * Return an integer denoting the maximum possible bitwise AND of any <span data-keyword="subset">subset</span> of size m after performing up to k operations optimally.
7 *  
8 * <strong class="example">Example 1:
9 * <div class="example-block">
10 * Input: <span class="example-io">nums = [3,1,2], k = 8, m = 2</span>
11 * Output: <span class="example-io">6</span>
12 * Explanation:
13 * 
14 * 	We need a subset of size m = 2. Choose indices [0, 2].
15 * 	Increase nums[0] = 3 to 6 using 3 operations, and increase nums[2] = 2 to 6 using 4 operations.
16 * 	The total number of operations used is 7, which is not greater than k = 8.
17 * 	The two chosen values become [6, 6], and their bitwise AND is 6, which is the maximum possible.
18 * </div>
19 * <strong class="example">Example 2:
20 * <div class="example-block">
21 * Input: <span class="example-io">nums = [1,2,8,4], k = 7, m = 3</span>
22 * Output: <span class="example-io">4</span>
23 * Explanation:
24 * 
25 * 	We need a subset of size m = 3. Choose indices [0, 1, 3].
26 * 	Increase nums[0] = 1 to 4 using 3 operations, increase nums[1] = 2 to 4 using 2 operations, and keep nums[3] = 4.
27 * 	The total number of operations used is 5, which is not greater than k = 7.
28 * 	The three chosen values become [4, 4, 4], and their bitwise AND is 4, which is the maximum possible.​​​​​​​
29 * </div>
30 * <strong class="example">Example 3:
31 * <div class="example-block">
32 * Input: <span class="example-io">nums = [1,1], k = 3, m = 2</span>
33 * Output: <span class="example-io">2</span>
34 * Explanation:
35 * 
36 * 	We need a subset of size m = 2. Choose indices [0, 1].
37 * 	Increase both values from 1 to 2 using 1 operation each.
38 * 	The total number of operations used is 2, which is not greater than k = 3.
39 * 	The two chosen values become [2, 2], and their bitwise AND is 2, which is the maximum possible.
40 * </div>
41 *  
42 * Constraints:
43 * 
44 * 	1 <= n == nums.length <= 5 * 10^4
45 * 	1 <= nums[i] <= 10^9
46 * 	1 <= k <= 10^9
47 * 	1 <= m <= n
48 * 
49 */
50pub struct Solution {}
51
52// problem: https://leetcode.com/problems/maximum-bitwise-and-after-increment-operations/
53// discuss: https://leetcode.com/problems/maximum-bitwise-and-after-increment-operations/discuss/?currentPage=1&orderBy=most_votes&query=
54
55// submission codes start here
56
57impl Solution {
58    pub fn maximum_and(nums: Vec<i32>, k: i32, m: i32) -> i32 {
59        0
60    }
61}
62
63// submission codes end
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_3806() {
71    }
72}
73