3495. Minimum Operations to Make Array Elements Zero
Approach
For each query range pair count non-zero groups; sum ceil(log4(max)) per group.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.
Bit manipulation uses bitwise operators (&, |, ^, ~, <<, >>) for compact and fast solutions. Key tricks: x & (x-1) clears lowest set bit, x ^ x = 0 (XOR cancellation), and bitmask DP represents subsets as integers. In C#, use int (32-bit) or long (64-bit) for bitmasking.
// Approach: For each query range pair count non-zero groups; sum ceil(log4(max)) per group.
// Time: O(q * log max) Space: O(1)
public class Solution
{
public long MinOperations(int[][] queries)
{
long ans = 0;
foreach (var query in queries)
{
int l = query[0];
int r = query[1];
ans += (GetOperations(r) - GetOperations(l - 1) + 1) / 2;
}
return ans;
}
// Returns the number of operations required for [1, n].
private long GetOperations(int n)
{
long res = 0;
int ops = 0;
for (int powerOfFour = 1; powerOfFour <= n; powerOfFour *= 4)
{
int l = powerOfFour;
int r = Math.Min(n, powerOfFour * 4 - 1);
res += (long)(r - l + 1) * ++ops;
}
return res;
}
}