3495. Minimum Operations to Make Array Elements Zero
Difficulty: Hard
Topics: Array
, Math
, Bit Manipulation
, Weekly Contest 442
You are given a 2D array queries
, where queries[i]
is of the form [l, r]
. Each queries[i]
defines an array of integers nums
consisting of elements ranging from l
to r
, both inclusive.
In one operation, you can:
- Select two integers
a
andb
from the array. - Replace them with
floor(a / 4)
andfloor(b / 4)
.
Your task is to determine the minimum number of operations required to reduce all elements of the array to zero for each query. Return the sum of the results for all queries.
Example 1:
- Input: queries = [[1,2],[2,4]]
- Output: 3
-
Explanation:
- For
queries[0]
:- The initial array is
nums = [1, 2]
. - In the first operation, select
nums[0]
andnums[1]
. The array becomes[0, 0]
. - The minimum number of operations required is 1.
- The initial array is
- For
queries[1]
:- The initial array is
nums = [2, 3, 4]
. - In the first operation, select
nums[0]
andnums[2]
. The array becomes[0, 3, 1]
. - In the second operation, select
nums[1]
andnums[2]
. The array becomes[0, 0, 0]
. - The minimum number of operations required is 2.
- The initial array is
- The output is
1 + 2 = 3
.
- For
Example 2:
- Input: queries = [[2,6]]
- Output: 4
-
Explanation:
- For queries[0]:
- The initial array is
nums = [2, 3, 4, 5, 6]
. - In the first operation, select
nums[0]
andnums[3]
. The array becomes[0, 3, 4, 1, 6]
. - In the second operation, select
nums[2]
andnums[4]
. The array becomes[0, 3, 1, 1, 1]
. - In the third operation, select
nums[1]
andnums[2]
. The array becomes[0, 0, 0, 1, 1]
. - In the fourth operation, select
nums[3]
andnums[4]
. The array becomes[0, 0, 0, 0, 0]
. - The minimum number of operations required is 4.
- The initial array is
- The output is 4.
- For queries[0]:
Constraints:
1 <= queries.length <= 105
queries[i].length == 2
queries[i] == [l, r]
1 <= l < r <= 109
Hint:
- For a number
x,
the number of"/4"
operations to change it to 0 isfloor(log4(x)) + 1
. - Always pair the 2 numbers with the maximum
"/4"
operations needed.
Solution:
We need to compute the minimum number of operations to reduce all numbers to zero. Here’s the plan:
Approach:
-
Precompute Ranges: For each possible value of
k
(the number of operations needed to reduce a number to zero), determine the range of numbers that require exactlyk
operations. This is done by noting that numbers in the range[4(k-1), 4k - 1]
requirek
operations. -
Process Queries: For each query
[l, r]
, calculate the total number of operationsT
needed by summing the contributions of all numbers in the range[l, r]
. Each number in a precomputed range[low, high]
contributesk
toT
. Also, track the maximumk
valueM
encountered in the range. -
Compute Operations: The minimum number of operations required for the query is the maximum of
ceil(T / 2)
andM
. This accounts for the fact that each operation can process two numbers, but a number requiringM
operations must be processed in at leastM
operations. - Sum Results: Sum the results for all queries and return the total.
Let's implement this solution in PHP: 3495. Minimum Operations to Make Array Elements Zero
<?php
/**
* @param Integer[][] $queries
* @return Integer
*/
function minOperations($queries) {
...
...
...
/**
* go to ./solution.php
*/
}
// Test cases
$queries1 = [[1,2],[2,4]];
echo minOperations($queries1) . PHP_EOL; // 3
$queries2 = [[2,6]];
echo minOperations($queries2) . PHP_EOL; // 4
?>
Explanation:
-
Precomputation: The code first precomputes the ranges of numbers that require exactly
k
operations to become zero. For eachk
from 1 to 16, it calculates the range[4(k-1), 4k - 1]
. -
Query Processing: For each query, it checks which precomputed ranges overlap with the query range
[l, r]
. For each overlapping range, it calculates the count of numbers in the overlap and addsk * count
to the total operationsS
. It also updates the maximumk
valueM
found in the query range. -
Operations Calculation: The number of operations needed for the query is the maximum of
ceil(S / 2)
andM
. This ensures that both the total steps and the maximum required steps for any number are considered. - Result Summation: The results for all queries are summed up and returned as the final answer.
This approach efficiently processes each query by leveraging precomputed ranges and ensures optimal performance even for large inputs. The complexity is linear with respect to the number of queries, making it suitable for the given constraints.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
Top comments (0)