Dsa
Bit Manipulation
Medium
The Bit-Flip Harvest
You are given an array of N integers. You can choose exactly one bit position B (0 to 30) and exactly one contiguous subarray [L, R]. For every element A[i] where L <= i <= R, you toggle bit B (if it was 0, it becomes 1; if it was 1, it becomes 0). Find the maximum possible sum of the array after this single operation.
Input Format:
An integer N, followed by N integers.
Output Format:
A single integer (the maximum sum).
Example:
Input:
4
1 2 4 8
Output:
18
(Explanation: Original sum is 15. Choose bit 0 and range [1, 3]. Elements 2, 4, 8 become 3, 5, 9. New sum: 1 + 3 + 5 + 9 = 18.)
Key concepts
bit_manipulationdynamic_programmingkadane
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now