Thursday, May 7, 2026

Costliest Data Plan (Medium Complexity Problem on Bit Manipulation)

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

  1. Count, for every bit position 0…30, how many plans have that bit set. Also record the overall OR.
  2. Build a “unique mask” containing all bits whose frequency is exactly 1.
  3. Any plan that shares no bit with this unique mask is removable (its bits are all covered by other plans).
  4. 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:

  1. Remove it temporarily

  2. Compute OR of all remaining plans

  3. 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:

1001
1001
1001
1001

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

ApproachTimeSpaceIdea
Bit-countO(N * 31)O(31)Track bit frequencies
Prefix/Suffix ORO(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:

1010

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

1010

The rightmost 1 is here:

   ^

So:

0010

gets extracted.


Next Line

Python
b = lsb.bit_length() - 1

This finds:

“Which bit position is this?”

Example:

0010

means bit position 1.

So:

Python
b = 1

Next

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:

1000

Rightmost ON bit is:

1000

Position = 3

Increase:

freq[3] += 1

Remove it:

1000 ^ 1000 = 0000

Now loop stops.


So What Happened Overall?

For number 10:

1010

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:

1010

The code repeatedly:

  1. Finds the first glowing bulb from the right

  2. Notes its position

  3. Turns it off

  4. Repeats until all bulbs are off

That’s exactly what this loop is doing.


Index of "Algorithms: Design and Analysis"    « Previous

How to survive layoffs?

See All Articles on Layoffs    « Previously    Next »


Career · Jobs · AI Economy

The Pink Slip
Survival Guide

Layoffs are no longer one-off crises — they have become the background hum of the modern economy. Here is how to keep your footing when the ground shifts beneath you.

May 20268 min read

When Job Cuts Become the Norm

It is hard to scroll through a business newsfeed today without stumbling onto another headline about corporate restructuring. Cognizant, the US-based IT giant, is reportedly planning to eliminate around 15,000 positions globally — with the heaviest cuts expected in India. Coinbase, the American crypto exchange, has announced it is slashing 14% of its workforce. PayPal is trimming 20% of its staff. These are not fringe cases. They are part of a gathering wave: more than 90,000 tech employees have already been handed pink slips so far in 2026 alone.

The common thread running through almost every announcement is artificial intelligence. A recent Gartner survey found that 80% of companies deploying AI are actively reducing headcount. This is the uncomfortable truth the industry is dancing around: AI is not just supplementing human work — in many roles, it is replacing it outright.

"Artificial intelligence is not assisting jobs. It is redesigning them — and in many cases, eliminating them entirely."

But here is what nobody tells you in those press releases: a layoff does not merely remove a salary. It dismantles routine. It chips away at confidence. One terse email, and suddenly a person is asking themselves questions they have no business asking — Was I not good enough? The answer, almost always, is no. Structural forces — automation cycles, cost pressures, macro headwinds — do not discriminate between the talented and the mediocre. They sweep wide.

What follows is not a lament about the job market. It is a practical guide for navigating it.

By the Numbers

Company Sector Jobs Cut Status
Cognizant IT Services ~15,000 globally Reported
Coinbase Crypto / Fintech 14% of workforce Announced
PayPal Payments 20% of staff Planned
Tech sector (2026 YTD) Multiple 90,000+ Confirmed
Statistic Finding Source
Companies using AI that are cutting staff 80% Gartner Survey
Job seekers who apply online ~82% Industry data
Online applicants who land an interview Only 2% Industry data

Five Steps to Come Back Stronger

These five principles are not feel-good platitudes. Each one addresses a specific, practical failure mode that makes the difference between a three-month gap on a résumé and a genuine career pivot.

01
Accept It — But Don't Resign to It

Denial is comfortable. It is also dangerous. Grieve the job — that is entirely valid — but do not pitch a tent inside the grief. There is a critical difference between acknowledging what happened and surrendering to it. You cannot fight a storm you refuse to see.

02
Upskill With Urgency

The same companies doing the cuts are investing heavily in AI, automation, and digital transformation. That is your roadmap. Prompt engineering, data analysis, cloud certifications, product thinking — pick a lane and persist. Your degree got you hired once. Your skills keep you employed.

03
Rebuild Your CV for Impact

Most résumés are packed with buzzwords and long paragraphs that say almost nothing. Lead with a single sentence that tells a hiring manager who you are in under ten seconds. Highlight impact, not duties. Recruiters do not read résumés — they scan them for value. Make sure that value is unmissable.

04
Network — For Real

Eighty-two percent of job seekers apply online. Only 2% land an interview that way. Think of online applications as crowded highways and referrals as fast lanes. Reach out to former managers, ex-colleagues, and mentors. Most roles are filled before they are ever posted publicly. Referrals are not just helpful — they are essential.

05
Protect Your Mental Health — Fiercely

A layoff can shake your identity to its core. The morning anxiety. The compulsive LinkedIn scrolling. The toxic comparisons to someone else's highlight reel. None of that helps. Build a daily routine. Move your body. Eat well. Reach out to people you trust. The currency of today's job market is adaptability — and adaptability requires a mind that is not running on empty.

A Note on the Mental Weight of Job Loss

It bears saying plainly: losing a job is a genuinely difficult life event, not merely a logistical inconvenience. Identity, self-worth, and social connection are all tied up in work in ways we rarely acknowledge until it is gone.

Practical habits that measurably help:

  • Maintain a structured daily schedule — even without a 9-to-5 anchoring it
  • Limit passive social media consumption, especially LinkedIn during vulnerable hours
  • Exercise consistently — even short walks count
  • Designate job-search hours rather than letting anxiety make it all-day
  • Talk to a friend, therapist, or peer group — isolation amplifies distress

Adaptability Is the New Job Security

Every wave of technological disruption — mechanisation, the internet, mobile — has produced its equivalent of today's headlines. Workers who treated the disruption as a signal to retool fared significantly better than those who waited for normalcy to return. It never quite returned; it evolved.

The AI transition is different in speed and scale, but not in kind. The roles being automated today are, broadly, those defined by repetition and pattern-matching. The roles being created require judgment, creativity, contextual understanding, and the very human capacity to manage AI systems effectively. The gap between those two categories is the upskilling opportunity hiding inside every redundancy notice.

People who use this moment to learn, reconnect, and rebuild do not just survive layoffs. They tend to emerge into roles that are more interesting, better compensated, and more durable than the ones they left.

What to Remember

  • Layoffs are increasingly structural, not personal — AI-driven restructuring affects entire functions, not just individuals.
  • Online job applications have a staggeringly low conversion rate (2%). Invest in human networks instead.
  • Upskilling is not optional — it is the direct counter to automation. Target skills the companies cutting jobs are simultaneously buying.
  • A well-crafted CV leads with impact, not job descriptions. Ten seconds is all a recruiter typically gives it.
  • Mental health is not a soft footnote — it is the precondition for effective job searching. Neglect it and every other step suffers.
  • The instinct to withdraw during a layoff is natural and almost always counterproductive. Visibility and connection are what accelerate re-employment.

Every résumé in circulation today once belonged to someone who was starting over. Success is not a checklist, and a career is not a competition scored against other people's LinkedIn timelines. Make room for fear. Make room for uncertainty. Just do not let either of them take the wheel.

The job market will reset — it always does. The question is only whether you will be ready when it does.


See All Articles on Layoffs    « Previously    Next » Tags: Layoffs,Interview Preparation,