Index of "Algorithms: Design and Analysis" « Previous

Basic Programming > Bit Manipulation > Basics of Bit Manipulation

Problem

Explanation

In the first case, the data plans cost 10rs and 5rs, With the first data plan(10rs) we can invite 1st and the 3rd friend because in the binary representation of 10  (1010) the first and the third bit are set, and with the second data plan (5rs), we can invite 0th and the 2nd friend because in the binary representation of 5(101), the 0th and the 2nd bit is set

Now with all the data plans, we could invite the 0th, 1st, 2nd, and 3rd friends, but if we remove any data plans, there will be a friend who will be left. Therefore the answer is 0rs

In the second case, the cost of all the data plans is the same, so if we remove any one data plan, we will still be able to invite all the friends we invited before. Therefore the answer is 9rs

Solve on HackerEarth

Note about the problem

Difficulty: Easy
Attempted by: 1441
Success Rate: 88%
Points Assigned: 20

Actual Complexity For Me: Medium/Hard

Prompt to DeepSeek/ChatGPT

I am learning Data Structures and Algorithms.

I will provide a screenshot of a problem statement.

Your task is NOT to directly give me the final code solution unless I explicitly ask for it.

Instead, please do the following:

1. First, carefully restate the problem in your own words to confirm correct understanding.
- If anything is unclear in the screenshot, ask me clarification questions before proceeding.

2. Identify:
- What category of problem this is (e.g., prefix sum, greedy, DP, two pointers, binary search, graph, etc.)
- What core DSA concepts are being tested
- What mathematical observations (if any) are involved
- What constraints are important and how they affect the approach

3. Explain:
- What naive/brute-force solution would look like
- Why that may or may not work under the given constraints
- What optimization insight is required

4. Clearly explain (*In Layman Terms In Explanatory Tone*) the key trick or insight needed to solve it.
- Why does that trick work?
- What pattern should I remember for future problems?

5. Provide:
- The time complexity and space complexity of the optimal approach
- Why it satisfies the constraints

6. If there are multiple valid approaches, compare them.

7. Only after all conceptual explanation, provide clean and correct Python code.

8. Avoid guessing unclear details.
- If any part of the screenshot is ambiguous, ask me instead of assuming.

Focus on correctness over speed. Be explicit in reasoning.

# OUTPUT SPECIFICATION

- Format your response as a HTML and return HTML file only.
- Wrap the HTML contents in a with class="customOuterWrapper"
- Write CSS rules starting with "div.customOuterWrapper ..." only
- Do not write any generic / global CSS rules.

Response from DeepSeek-V3 (Deep Think as Expert)

Problem Restatement

Pawan has friends labeled by unique non‑negative integers 0, 1, 2, … He buys N data plans. Each plan i has a cost aᵢ (a non‑negative integer). When Pawan uses a plan with cost Y, a friend f receives an invitation if and only if the f‑th bit (0‑indexed) in the binary representation of Y is 1. A friend attends the party if they receive at least one invitation from any plan.

The set of all invited friends is exactly the bitwise OR of all plan costs. Pawan wants to remove at most one data plan and still invite exactly the same set of friends as before. The money saved is the cost of the removed plan. We must find the maximum possible cost he can save. If no plan can be removed without losing some friend, the answer is 0.

1. Problem Category & Core Concepts

Category: Bit manipulation / Greedy.
Core DSA: Bitwise operations (OR, AND, bit counting), frequency maps, set‑wise reasoning.
Mathematical Observation: The set of invited friends is the union of the bits set in any plan. Removing a plan is safe iff every bit that plan provides is also provided by at least one other plan.
Constraints:
- Test cases t ≤ 100, sum of N ≤ 10⁶.
- Each aᵢ ≤ 10⁹ → fits in 30 bits (0…29).
- Time limit implies we need O(bit‑length ⋅ total N) or better.

2. Naïve / Brute‑Force Approach

For each data plan, remove it, compute the bitwise OR of the remaining plans, and compare with the original total OR. If they match, the plan is “removable”. Take the maximum cost among all removable plans.

Complexity: O(N²) per test case (computing OR for each removal), which is far too slow when N is large (total N ≤ 10⁶ would become ~10¹² operations).

3. Key Insight & Optimisation

Instead of recomputing the whole OR every time, notice that a plan is only essential if it is the sole provider of at least one bit that is set in the total OR. In other words:

A plan can be removed if and only if it has NO bit for which it is the only plan with that bit set.

Why does this work?

Every friend (bit) that was invited originally must still receive an invitation.
If a bit is set in at least two plans, we can drop any one of them and the bit remains present.
If a bit is set in exactly one plan, dropping that plan makes that bit disappear → the set of invited friends shrinks.

Pattern to remember: “Union preservation under removal of one element” is equivalent to checking which elements own a “unique” property (a bit that appears exactly once). This pattern appears often in problems involving OR/AND/XOR and frequency counts over bits.

4. Step‑by‑Step Optimal Algorithm

Count, for every bit position 0…30, how many plans have that bit set. Also record the overall OR.
Build a “unique mask” containing all bits whose frequency is exactly 1.
Any plan that shares no bit with this unique mask is removable (its bits are all covered by other plans).
Answer = maximum cost among all removable plans; 0 if none exist.

Complexity:

Time: O( (number of set bits in all numbers) + N + 31 ) ≈ O(31·N) worst‑case. With total N ≤ 10⁶ this is ~3×10⁷ operations, well within limits.
Space: O(31) for the frequency array → O(1) extra space.

5. Python Implementation

import sys

def solve() -> None:
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    t = int(next(it))
    out_lines = []
    
    for _ in range(t):
        n = int(next(it))
        a = [int(next(it)) for _ in range(n)]
        
        # 10^9 < 2^30, so bits 0..29 are enough; using 31 for safety
        freq = [0] * 31
        
        for x in a:
            v = x
            # iterate over set bits only
            while v:
                lsb = v & -v
                b = lsb.bit_length() - 1
                freq[b] += 1
                v ^= lsb   # clear the lowest set bit
        
        # Build mask of bits that occur in exactly one plan
        unique_mask = 0
        for b in range(31):
            if freq[b] == 1:
                unique_mask |= (1 << b)
        
        best_saving = 0
        for x in a:
            # If x has no unique bit, it can be dropped
            if (x & unique_mask) == 0:
                if x > best_saving:
                    best_saving = x
        
        out_lines.append(str(best_saving))
    
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    solve()

6. Example Walkthrough

Case 1: plans = [10, 5] → bits: 10=1010₂, 5=0101₂. OR = 1111₂. Every bit appears exactly once → unique_mask = 1111₂. Both plans touch it → none removable → answer 0.
Case 2: plans = [9, 9, 9, 9] (or four equal costs). Bits of 9=1001₂ appear 4 times each → unique_mask = 0. All plans are removable → answer 9 (the cost).

Key Takeaway: When dealing with “can I remove one element without changing a bitwise OR / union”, count how many elements supply each bit and identify the elements that are the sole supplier of at least one bit. The rest are safe to remove.


def solve():
    t = int(input())

    for _ in range(t):

        n = int(input())

        a = list(map(int, input().split()))

        # frequency of each bit
        freq = [0] * 31

        for x in a:
            v = x

            # iterate over set bits only
            while v:
                lsb = v & -v
                b = lsb.bit_length() - 1

                freq[b] += 1

                v ^= lsb

        # mask containing bits that appear exactly once
        unique_mask = 0

        for b in range(31):
            if freq[b] == 1:
                unique_mask |= (1 << b)

        best_saving = 0

        for x in a:

            # removable if it contributes no unique bit
            if (x & unique_mask) == 0:

                if x > best_saving:
                    best_saving = x

        print(best_saving)


if __name__ == "__main__":
    solve()

Time (sec): 0.82564
Memory (KiB): 11824

A Slightly Simpler Implementation (Just one Modification)


def solve():
    t = int(input())

    for _ in range(t):

        n = int(input())

        a = list(map(int, input().split()))

        # frequency of each bit
        freq = [0] * 31

        for x in a:
            for b in range(31):
                if x & (1 << b):
                    freq[b] += 1
            

        # mask containing bits that appear exactly once
        unique_mask = 0

        for b in range(31):
            if freq[b] == 1:
                unique_mask |= (1 << b)

        best_saving = 0

        for x in a:

            # removable if it contributes no unique bit
            if (x & unique_mask) == 0:

                if x > best_saving:
                    best_saving = x

        print(best_saving)


if __name__ == "__main__":
    solve()

Time (sec): 1.09442
Memory (KiB): 14348

Conversation Log With ChatGPT 5.3

Here’s the problem in plain words:

You have N data plans. Each plan number is also a bitmask of friends it can notify: if bit i is set in a plan’s value, then friend i gets notified by that plan.

Pawan wants to remove at most one plan and still notify exactly the same set of friends as before. Since the cost of a plan is equal to its value, the amount of money saved is the value of the removed plan. Your job is to find the maximum cost plan that can be removed without changing the set of notified friends. If no plan can be removed, answer is 0.

1) What kind of problem is this?

This is mainly:

Bit manipulation
Greedy / checking redundancy
A little like set coverage using bits

2) Core DSA concepts being tested

Bitwise OR
Counting how many numbers contain each bit
Checking whether an element is “essential” or “redundant”

3) Important mathematical observation

The total set of notified friends is just the bitwise OR of all plans.

A plan can be removed iff every bit set in that plan is also present in at least one other plan.

Why?
Because if a bit appears only in that one plan, removing it would make that friend lose notification.

So the condition for a plan a[i] to be removable is:

for every bit set in a[i], the count of that bit across the whole array is at least 2

4) Brute force idea

For every plan:

Remove it temporarily
Compute OR of all remaining plans
Compare with original OR

Why brute force is too slow

If you do this by scanning the whole array for every index, that becomes O(N^2) in the worst case.

With N up to 10^5, that is too slow.

5) Key optimization / trick

Instead of recomputing OR again and again, count how many times each bit appears in the whole array.

Then for each number:

look at its set bits
if all those bits have frequency > 1, the number is removable

This works because OR is just a union of bits.
A bit disappears only if the removed number was the only one containing it.

Pattern to remember

Whenever a problem says:

“remove one element”
“still preserve the same OR / union / coverage”

think:

“Check whether every feature of that element is covered by others.”

6) Multiple valid approaches

Approach 1: Bit counts

Best and simplest here
Time: O(N * 31)
Space: O(31)

Approach 2: Prefix OR / suffix OR

Compute OR before each index and after each index
Then OR of all except i can be found quickly
Time: O(N)
Space: O(N)

For this problem, bit counts are cleaner because values are up to 1e9, so only about 31 bits matter.

7) Complexity

Let B = 31 because a[i] <= 10^9.

Time: O(N * B)
Space: O(B)

This easily fits the constraints because 31 * 10^5 is small enough.

8) Python code

Python
import sys

def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    t = data[0]
    idx = 1
    out = []

    for _ in range(t):
        n = data[idx]
        idx += 1
        arr = data[idx:idx + n]
        idx += n

        # Count how many numbers contain each bit
        bit_count = [0] * 31  # enough for ai <= 1e9

        for x in arr:
            b = 0
            while x:
                if x & 1:
                    bit_count[b] += 1
                x >>= 1
                b += 1

        ans = 0

        for x in arr:
            removable = True
            temp = x
            b = 0
            while temp:
                if temp & 1:
                    if bit_count[b] == 1:
                        removable = False
                        break
                temp >>= 1
                b += 1

            if removable:
                if x > ans:
                    ans = x

        out.append(str(ans))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    solve()

If you want, I can also show a prefix/suffix OR version and explain why it works on the same sample.

Let’s understand the prefix/suffix OR approach carefully.

Core Idea

Suppose you want to know:

“What is the OR of all elements except index i?”

Instead of recomputing it every time, precompute:

prefix[i] = OR of elements from 0 to i
suffix[i] = OR of elements from i to n-1

Then:


OR of all except i
=
prefix[i-1] OR suffix[i+1]

This is a very common technique in DSA:

“Precompute information from left and right so removing one element becomes O(1).”

Step-by-Step Example

Suppose:


arr = [10, 5]

Binary:


10 = 1010
5  = 0101

Total OR:


1010
0101
----
1111 = 15

So originally all friends represented by bits 0,1,2,3 are notified.

Build Prefix OR


prefix[0] = 10

prefix[1] = prefix[0] | arr[1]
          = 10 | 5
          = 15

So:


prefix = [10, 15]

Build Suffix OR


suffix[1] = 5

suffix[0] = arr[0] | suffix[1]
          = 10 | 5
          = 15

So:


suffix = [15, 5]

Remove Each Element

Remove index 0

OR of remaining:


suffix[1] = 5

Compare with total OR:


5 != 15

So cannot remove 10.

Remove index 1

OR of remaining:


prefix[0] = 10

Compare:


10 != 15

Cannot remove 5.

Answer = 0.

Another Example


arr = [9, 9, 9, 9]

Binary:

Total OR = 9.

If we remove any one element:

Remaining OR still = 9.

So maximum removable = 9.

Why This Works

Bitwise OR has this important property:


(A OR B OR C OR D)
without C
=
(prefix before C) OR (suffix after C)

Because OR is:

associative
commutative

Same pattern appears in:

product except self
sum except self
XOR except self
max/min outside range

Complexity

Building prefix

O(N)

Building suffix

O(N)

Checking all removals

O(N)

Total:


Time:  O(N)
Space: O(N)

Comparison With Bit Count Approach

Approach	Time	Space	Idea
Bit-count	O(N * 31)	O(31)	Track bit frequencies
Prefix/Suffix OR	O(N)	O(N)	Compute OR except self

Which One Is Better Here?

Bit-count approach

Pros:

Less memory
More “bit-manipulation oriented”
Elegant

Cons:

Slightly trickier to think about initially

Prefix/Suffix approach

Pros:

Easier to generalize
Cleaner conceptually
Very reusable pattern

Cons:

Uses extra arrays

Prefix/Suffix OR Code

Python
import sys

def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    t = data[0]
    idx = 1

    answers = []

    for _ in range(t):
        n = data[idx]
        idx += 1

        arr = data[idx:idx + n]
        idx += n

        # Build prefix OR
        prefix = [0] * n
        prefix[0] = arr[0]

        for i in range(1, n):
            prefix[i] = prefix[i - 1] | arr[i]

        # Build suffix OR
        suffix = [0] * n
        suffix[-1] = arr[-1]

        for i in range(n - 2, -1, -1):
            suffix[i] = suffix[i + 1] | arr[i]

        total_or = prefix[-1]

        ans = 0

        for i in range(n):

            if n == 1:
                remaining_or = 0

            elif i == 0:
                remaining_or = suffix[1]

            elif i == n - 1:
                remaining_or = prefix[n - 2]

            else:
                remaining_or = prefix[i - 1] | suffix[i + 1]

            if remaining_or == total_or:
                ans = max(ans, arr[i])

        answers.append(str(ans))

    print("\n".join(answers))

if __name__ == "__main__":
    solve()

A very important takeaway pattern from this problem:

If a question asks:
“What happens if I remove one element?”

Think about:

prefix/suffix preprocessing

frequency counting

contribution of each element

That pattern appears constantly in DSA interviews and contests.

what is this code doing:

 for x in a:
            v = x

            # iterate over set bits only
            while v:
                lsb = v & -v
                b = lsb.bit_length() - 1

                freq[b] += 1

                v ^= lsb


Explain in layman terms

This code is doing one specific job:

“For every number, find which bits are ON (1), and count them.”

But it does it in a very clever and efficient way.

Let’s break it down slowly in plain English.

First: What is a “set bit”?

A set bit means a bit that is 1.

Example:


10 = 1010

Bits ON are:

bit 1
bit 3

(Counting from right starting at 0)

Goal of this code

Suppose:

Python
a = [10, 5]

Binary:


10 = 1010
5  = 0101

We want to count:


bit 0 appears how many times?
bit 1 appears how many times?
bit 2 appears how many times?
...

The Code

Python
for x in a:
    v = x

    while v:
        lsb = v & -v
        b = lsb.bit_length() - 1

        freq[b] += 1

        v ^= lsb

Now let’s understand each line.

Step 1

Python
for x in a:

Take each number one by one.

Example:


x = 10

Step 2

Python
v = x

Make a copy because we will modify it.

So:


v = 10

Binary:

Step 3

Python
while v:

Keep going while the number is not zero.

The Important Trick

Python
lsb = v & -v

This extracts the rightmost ON bit.

Example

Suppose:


v = 1010

Then:


lsb = 0010

Why?

Because this trick isolates the lowest set bit.

Visual Intuition

The rightmost 1 is here:

So:

gets extracted.

Next Line

Python
b = lsb.bit_length() - 1

This finds:

“Which bit position is this?”

Example:

means bit position 1.

So:

Python
b = 1

Python
freq[b] += 1

Increase count for that bit.

Meaning:


bit 1 appeared once more

Final Trick

Python
v ^= lsb

This removes that bit from the number.

Example:


1010
^0010
-----
1000

Now:


v = 1000

The lowest set bit was removed.

Loop Continues

Again:

Rightmost ON bit is:

Position = 3

Increase:


freq[3] += 1

Remove it:


1000 ^ 1000 = 0000

Now loop stops.

So What Happened Overall?

For number 10:

We found:

bit 1 is ON
bit 3 is ON

WITHOUT checking all 31 bits.

Why Is This Clever?

A beginner solution would do:

Python
for b in range(31):
    if x & (1 << b):
        freq[b] += 1

This checks EVERY bit.

Even if only 2 bits are ON.

This Optimized Version

Checks ONLY the ON bits.

If a number has:

2 set bits → only 2 iterations
5 set bits → only 5 iterations

Much faster.

Main Pattern to Remember

These are classic bit tricks:

1. Extract lowest set bit

Python
x & -x

Meaning:

“Give me the rightmost 1-bit.”

2. Remove lowest set bit

Python
x ^= (x & -x)

or equivalently:

Python
x &= (x - 1)

Meaning:

“Delete the rightmost 1-bit.”

Layman Analogy

Imagine a number as a row of glowing bulbs:

The code repeatedly:

Finds the first glowing bulb from the right
Notes its position
Turns it off
Repeats until all bulbs are off

That’s exactly what this loop is doing.

Index of "Algorithms: Design and Analysis" « Previous

Pages

Thursday, May 7, 2026

Costliest Data Plan (Medium Complexity Problem on Bit Manipulation)

Basic Programming > Bit Manipulation > Basics of Bit Manipulation

Problem

Explanation

Note about the problem

Prompt to DeepSeek/ChatGPT

Response from DeepSeek-V3 (Deep Think as Expert)

Problem Restatement

1. Problem Category & Core Concepts

2. Naïve / Brute‑Force Approach

3. Key Insight & Optimisation

4. Step‑by‑Step Optimal Algorithm

5. Python Implementation

6. Example Walkthrough

Time (sec): 0.82564 Memory (KiB): 11824

A Slightly Simpler Implementation (Just one Modification)

Time (sec): 1.09442 Memory (KiB): 14348

Conversation Log With ChatGPT 5.3

1) What kind of problem is this?

2) Core DSA concepts being tested

3) Important mathematical observation

4) Brute force idea

Why brute force is too slow

5) Key optimization / trick

Pattern to remember

6) Multiple valid approaches

Approach 1: Bit counts

Approach 2: Prefix OR / suffix OR

7) Complexity

8) Python code

Core Idea

Step-by-Step Example

Build Prefix OR

Build Suffix OR

Remove Each Element

Remove index 0

Remove index 1

Another Example

Why This Works

Complexity

Building prefix

Building suffix

Checking all removals

Comparison With Bit Count Approach

Which One Is Better Here?

Bit-count approach

Prefix/Suffix approach

Prefix/Suffix OR Code

First: What is a “set bit”?

Goal of this code

The Code

Step 1

Step 2

Step 3

The Important Trick

Example

Visual Intuition

Next Line

Next

Final Trick

Loop Continues

So What Happened Overall?

Why Is This Clever?

This Optimized Version

Main Pattern to Remember

1. Extract lowest set bit

2. Remove lowest set bit

Layman Analogy