Parity-Binary Sort (Super Easy in Python)

Index of "Algorithms: Design and Analysis"
<<< Previous    Next >>>

Basic Programming> Bit Manipulation> Basics of Bit Manipulation

Solve on HackerEarth

Problem

You are given an array $A$ of $N$ integers. Your task is to implement a sorting algorithm that arranges the numbers in the array based on following conditions and return that array:
1. Numbers with an even count of set bits should appear first in ascending order.
2. Following that, numbers with an odd count of set bits should be arranged in ascending order.

Input Format:

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

The first line contains $T$ denoting the number of test cases. $T$ also specifies the number of times you have to run the solve function on a different set of inputs.
For each test case:

• The first line contains the integer $N$.
• The second line contains the array $A$ of length $N$

Output Format:
For each test case, print the answer in a new line. 

Constraints:

$1 \leq T \leq 10 \\ 1 \leq N \leq 10^5 \\ 1 \leq A[i] \leq 10^5$

Sample Input

1
6
5 2 8 12 7 6

Sample Output

5 6 12 2 7 8

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

Given the input array [5, 2, 8, 12, 7, 6], the output should be [5, 6, 12, 2, 7, 8], as:
Numbers with an even count of set bits: 5(101), 6(110), 12(1100)
Numbers with an odd count of set bits: 2(10), 7(111), 8(100)

Contributers:

Vinayak Mishra

Madhumeeta Bauk

---

---

My Code

def solve(A):
    evens = [i for i in A if i.bit_count() % 2 == 0]
    odds = [i for i in A if i.bit_count() % 2 != 0]

    evens.sort()
    odds.sort()

    final = evens + odds
    return ' '.join(map(str, final))

T = int(input())

for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    print(solve(A))

---

---

Revising Binary Sort (Though we used Python built-in in the code)

help me revise binary sort algorithm

Sure 👍 Let’s revise Binary Sort properly and clearly.

But first — when people say Binary Sort, they usually mean one of these two things:

1. Binary Insertion Sort (Insertion sort optimized using Binary Search)

2. Sorting Binary Array (0s and 1s only)

I’ll cover both so you're fully prepared for interviews and DSA practice.

---

1️⃣ Binary Insertion Sort (Important for DSA)

🔹 Idea

Normal Insertion Sort:

• Pick element

• Compare backwards

• Shift elements

• Insert at correct place

Binary Insertion Sort:

• Use Binary Search to find correct position

• Still shift elements manually

⚠ Important:

• Comparisons reduce to O(n log n)

• But shifting still makes overall complexity O(n²)

---

🔹 Algorithm Steps

For each element from index 1 → n-1:

1. Store current element as key

2. Use binary search in sorted portion [0 … i-1]

3. Find correct index pos

4. Shift elements right

5. Insert key at pos

---

🔹 Example

Array:

Code
[5, 2, 4, 6, 1]

Step 1:
Sorted part: [5]
Insert 2 → Binary search → position 0
Array → [2, 5, 4, 6, 1]

Step 2:
Sorted part: [2, 5]
Insert 4 → position 1
Array → [2, 4, 5, 6, 1]

Continue...

Final:

Code
[1, 2, 4, 5, 6]

---

🔹 Python Implementation

Python
def binary_search(arr, key, start, end):
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] > key:
            end = mid - 1
        else:
            start = mid + 1
    return start

def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        pos = binary_search(arr, key, 0, i - 1)
        
        # shift elements
        arr = arr[:pos] + [key] + arr[pos:i] + arr[i+1:]
        
    return arr

---

🔹 Time Complexity

Case	Complexity
Best	O(n log n) comparisons
Worst	O(n²) shifts
Overall	O(n²)

---

2️⃣ Sorting Binary Array (0s and 1s Only)

If array contains only 0 and 1:

Example:

Code
[1, 0, 1, 0, 0, 1]

Method 1: Counting (Simple)

Python
def sort_binary(arr):
    count_zero = arr.count(0)
    return [0]*count_zero + [1]*(len(arr) - count_zero)

Time: O(n)

---

Method 2: Two Pointer (Interview Favorite)

Python
def sort_binary(arr):
    left = 0
    right = len(arr) - 1
    
    while left < right:
        if arr[left] == 1:
            arr[left], arr[right] = arr[right], arr[left]
            right -= 1
        else:
            left += 1
    
    return arr

Time: O(n)
Space: O(1)

---

🧠 When Is Binary Insertion Sort Useful?

• When comparisons are very expensive

• When dataset is small

• When array is almost sorted

• Used internally in hybrid algorithms (like Timsort conceptually)

---

🔥 Interview Summary Answer

If interviewer asks:

What is Binary Sort?

You say:

Binary Insertion Sort is an optimization of insertion sort where we use binary search to find the correct position of an element in the sorted part of the array. It reduces comparisons to O(n log n) but shifting still makes overall time complexity O(n²).

---

If you'd like, I can:

• 🔹 Compare it with Merge Sort / Quick Sort

• 🔹 Give dry run practice questions

• 🔹 Give optimized in-place version

• 🔹 Explain mathematically why it’s still O(n²)

What level are you preparing for — college exam, coding round, or advanced DSA?

---

---

Explain mathematically why it’s still O(n²)

Great — this is the exact kind of thinking interviewers love. Let’s break it down mathematically and cleanly.

We’re analyzing Binary Insertion Sort.

---

🔎 Step 1: What Actually Changes?

Normal Insertion Sort:

• Find correct position → O(i) comparisons

• Shift elements → O(i)

Binary Insertion Sort:

• Find position using binary search → O(log i) comparisons

• Shift elements → O(i)

So only comparisons improve, not shifting.

---

🔎 Step 2: Count Total Work Precisely

For an array of size n.

At step i, worst case:

• Binary search cost = O(log i)

• Shifting cost = O(i)

Total cost at step i:

Code
T(i) = log i + i

---

🔎 Step 3: Total Cost Over All Iterations

We sum from i = 1 to n-1.

$$T(n) = \sum_{i=1}^{n-1} (\log i + i)$$

Break into two sums:

$$T(n) = \sum \log i + \sum i$$

---

Part A: Sum of log i

$$\sum_{i=1}^{n} \log i = \log(n!)$$

Using Stirling’s approximation:

$$\log(n!) ≈ n \log n$$

So:

$$\sum \log i = O(n \log n)$$

---

Part B: Sum of i

$$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$$

Which simplifies to:

$$O(n^2)$$

---

🔎 Step 4: Combine Both

$$T(n) = O(n \log n) + O(n^2)$$

Now compare growth rates:

$$n^2 \gg n \log n$$

As n becomes large:

$$\frac{n^2}{n \log n} = \frac{n}{\log n} \to \infty$$

So n² dominates.

---

✅ Final Mathematical Conclusion

$$T(n) = O(n^2)$$

Because:

• Comparisons = O(n log n)

• Shifting = O(n²)

• Dominant term = O(n²)

---

🧠 Intuition (Very Important)

Binary search helps you find where to insert.

But it does NOT help you move elements.

In an array:

To insert at index 0, you must shift n elements.

That physical movement costs linear time.

And that happens n times.

So:

$$n \times n = n^2$$

---

🔥 Interview One-Liner

Even though binary search reduces comparisons to O(n log n), insertion still requires shifting elements which costs O(n) per iteration. Summing over all iterations gives O(n²), which dominates the total complexity.

---

If you'd like, I can now:

• Prove why linked list version behaves differently

• Compare with Merge Sort mathematically

• Show graphical growth comparison

• Or derive the exact average-case complexity mathematically

What depth are you aiming for?

Hamming Sort - sorting based on count of differing bits in the binary representations of two integers (Easy)

Index of "Algorithms: Design and Analysis"
<<< Previous    Next >>>

Basic Programming > Bit Manipulation > Basics of Bit Manipulation

Solve on HackerEarth

Problem

Given an array of integers, denoted as $A$, and an integer $K$, your task is to implement a sorting algorithm. The goal is to arrange the elements in $A$ based on their Hamming Distance from the integer $K$.

The Hamming Distance is defined as the count of differing bits in the binary representations of two integers.

The sorting should be done in ascending order of Hamming distance, and in case of a tie in Hamming Distances, the elements should be sorted in ascending numerical order.

Input Format:

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

The first line contains $T$ denoting the number of test cases. $T$ also specifies the number of times you have to run the solve function on a different set of inputs. For each test case:

• The first line contains the integer $N$ and $K$.
• The second line contains the array $A$ of length $N$

Output Format: For each test case, print the answer in a new line. 

Constraints:

$1 \leq T \leq 10 \\ 1 \leq N \leq 10^5 \\ 1 \leq K \leq 10^5 \\ 1 \leq A[i] \leq 10^5$

Sample Input

1
3 2
4 5 6

Sample Output

6 4 5

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

In the example, binary representation of $K = 2$ is "$10$". Similarly for array $[4,5,6]$, the binary representation is $[100, 101, 110]$. Now the hamming distance of each element of the array with $K$ are $[2,3,1]$. Hence sorting on the basis of Hamming Distance, the final output comes out to be $[6,4,5]$.

Contributers:

Vinayak Mishra

Madhumeeta Bauk

---

---

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

1) Restating the problem (in my own words)

For each test case, you’re given:

• an array A of N integers

• an integer K

You must sort the array A using this key:

1. Primary key: the Hamming distance between A[i] and K

2. Tie-breaker: if two elements have the same Hamming distance, the smaller number comes first

Here, Hamming distance between two integers means:

the number of bit positions where their binary representations differ.

So you output the sorted array for each test case on a new line.

Nothing in the screenshot seems ambiguous enough to block solving, so I’ll proceed.

---

2) What type of problem is this?

Category

• Sorting with a custom key

• Uses bit manipulation (XOR + popcount)

Core DSA concepts being tested

• Defining a correct comparison/key for sorting

• Bitwise XOR

• Counting set bits (popcount)

• Handling constraints efficiently (N up to 1e5)

Key mathematical / bit observation

For integers x and K:

• Bits differ exactly where x XOR K has a 1

• Therefore:
  HammingDistance(x, K) = popcount(x XOR K)

This avoids manually comparing binary strings.

Important constraints & impact

• 1 ≤ T ≤ 10

• 1 ≤ N ≤ 10^5 per test

• Values up to 10^5

Main cost is sorting: O(N log N) per test, which is fine at 1e5 scale.

---

3) Naive / brute-force approach

What brute force looks like

For each element:

1. Convert x and K to binary strings

2. Pad with leading zeros to equal length

3. Count positions where they differ

4. Sort by (distance, x)

Why it may be suboptimal

• Binary conversion + padding per element adds overhead

• Still ends up sorting, so you’re paying extra constant factors for no benefit

It might pass, but it’s not the cleanest or most robust approach under tight time limits.

---

4) The key trick / insight

Trick

Use:

• d = (x ^ K) to mark differing bit positions

• popcount(d) to count how many positions differ

So you sort by:

Plain text
(popcount(x XOR K), x)

Why it works

• XOR outputs 1 exactly when bits differ

• Counting 1s gives the number of differing positions → the Hamming distance

Pattern to remember

Whenever you see:

• “differing bits”

• “Hamming distance of integers”

• “bit positions that differ”

Think immediately:

Hamming distance = popcount(a XOR b)

---

5) Complexity of the optimal approach

For each test case:

• Compute distances: O(N) (each popcount is very fast)

• Sort: O(N log N)

• Extra space: O(N) if you store (key, value) pairs, or O(1) extra if sorting in-place with a key function (Python still allocates some overhead internally)

This satisfies constraints for N = 1e5.

---

6) Multiple valid approaches (comparison)

Approach A (recommended): sort with key = (popcount(x^K), x)

• Simple, clean

• Fast in practice

Approach B: stable sort twice

1. Sort numerically

2. Stable sort by Hamming distance

• Works because Python sort is stable

• Slightly more verbose, sometimes useful if tie-breaking rules get more complex

Approach A is the most direct.

---

7) Python code (after concepts)

Python
import sys

def popcount(x: int) -> int:
    # Python 3.8+ has int.bit_count() (actually added in 3.8/3.10 depending on env);
    # fall back safely if unavailable.
    try:
        return x.bit_count()
    except AttributeError:
        return bin(x).count("1")

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

    for _ in range(t):
        n = int(data[idx]); k = int(data[idx + 1]); idx += 2
        arr = list(map(int, data[idx:idx + n])); idx += n

        arr.sort(key=lambda x: (popcount(x ^ k), x))
        out_lines.append(" ".join(map(str, arr)))

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

if __name__ == "__main__":
    solve()

If you want, I can also walk you through a dry run on the sample [4,5,6] with K=2 and show exactly how the keys become (2,4), (3,5), (1,6) → output 6 4 5.

---

---

modify your code to adapt to this boilerplate code:

def solve (N, K, A):
    # Write your code here
    pass

T = int(input())
for _ in range(T):
    custom_input_1 = list(map(str, input().split()))
    N = int(custom_input_1[0])
    K = int(custom_input_1[1])
    A = list(map(int, input().split()))

    out_ = solve(N, K, A)
    print (' '.join(map(str, out_)))

Sure — here’s the same logic adapted to your exact boilerplate (no extra I/O tricks, just implement solve):

Python
def solve(N, K, A):
    # Sort by (HammingDistance(A[i], K), A[i])
    # HammingDistance(x, K) = popcount(x XOR K)
    A.sort(key=lambda x: ((x ^ K).bit_count(), x))
    return A

T = int(input())
for _ in range(T):
    custom_input_1 = list(map(str, input().split()))
    N = int(custom_input_1[0])
    K = int(custom_input_1[1])
    A = list(map(int, input().split()))

    out_ = solve(N, K, A)
    print(' '.join(map(str, out_)))

If your Python version doesn’t support .bit_count(), tell me which version you’re using and I’ll swap in a compatible popcount.

---

---

can you explain this line a bit more clearly in layman terms:

A.sort(key=lambda x: ((x ^ K).bit_count(), x))

Absolutely.

What A.sort(key=...) means

sort() rearranges the list.
The key= part tells Python: “For each element, compute a value (a ‘sorting label’). Sort by that label instead of the element itself.”

So here, for every number x in A, we compute a pair (tuple):

Python
((x ^ K).bit_count(), x)

Python sorts tuples like this:

1. Compare the first value

2. If tied, compare the second value

---

Breaking down the key: ((x ^ K).bit_count(), x)

1) x ^ K (XOR)

XOR compares bits of x and K:

• If a bit is the same → result bit is 0

• If a bit is different → result bit is 1

So x ^ K produces a number whose 1 bits mark exactly the positions where x and K differ.

Example: x=4 (100), K=2 (010)

Code
  100
^ 010
= 110

They differ in two positions → 110 has two 1s.

2) .bit_count()

This counts how many 1 bits are in the binary form of a number.

So:

Python
(x ^ K).bit_count()

= number of differing bit positions
= Hamming distance between x and K

3) , x (tie-breaker)

If two numbers have the same Hamming distance from K, we want the smaller number first — that’s why we include x as the second item in the tuple.

---

In plain English

This line tells Python:

“Sort the array by how many bits differ from K (fewest differences first).
If two numbers differ by the same amount, put the smaller number first.”

---

Tiny example

Let K = 2, A = [4, 5, 6]

Compute the key for each x:

• x=4: 4^2 = 6 (110), bit_count = 2 → key (2, 4)

• x=5: 5^2 = 7 (111), bit_count = 3 → key (3, 5)

• x=6: 6^2 = 4 (100), bit_count = 1 → key (1, 6)

Sort by keys → (1,6), (2,4), (3,5) → result [6, 4, 5]

If you want, I can also rewrite that lambda into a named function (often clearer when learning).