Orray (Codeforces 1742G)
Tags: Greedy, bitmasks

You are given an array $$$a$$$ consisting of $$$n$$$ nonnegative integers. Let's define the prefix OR array $$$b$$$ as the array $$$b_i = a_1~\mathsf{OR}~a_2~\mathsf{OR}~\dots~\mathsf{OR}~a_i$$$, where $$$\mathsf{OR}$$$ represents the bitwise OR operation. In other words, the array $$$b$$$ is formed by computing the $$$\mathsf{OR}$$$ of every prefix of $$$a$$$.You are asked to rearrange the elements of the array $$$a$$$ in such a way that its prefix OR array is lexicographically maximum.An array $$$x$$$ is lexicographically greater than an array $$$y$$$ if in the first position where $$$x$$$ and $$$y$$$ differ, $$$x_i > y_i$$$.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the array $$$a$$$.The second line of each test case contains $$$n$$$ nonnegative integers $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case print $$$n$$$ integers — any rearrangement of the array $$$a$$$ that obtains the lexicographically maximum prefix OR array.


Sample Inputs:
5
4
1 2 4 8
7
5 1 2 3 4 5 5
2
1 101
6
2 3 4 2 3 4
8
1 4 2 3 4 5 7 1

Sample Outputs:
8 4 2 1 
5 2 1 3 4 5 5 
101 1 
4 3 2 2 3 4 
7 1 4 2 3 4 5 1

Solution (Python):
MAX_BITS = 32

def to_bin(dec_number):
    return bin(dec_number).replace('0b', '')

def pick_best(dec_numbers, or_prefix_dec):
    best_result = 0
    best_dec_pick = None
    best_pick_index = None
    for (index, dec_number) in dec_numbers.items():
        result = or_prefix_dec | dec_number
        if result > best_result:
            best_result = result
            best_dec_pick = dec_number
            best_pick_index = index
    return (best_dec_pick, best_pick_index)

def solve():
    t = int(input())
    for _ in range(t):
        _ = int(input())
        dec_numbers = list(map(int, input().split()))
        dec_numbers = {index: number for (index, number) in enumerate(dec_numbers)}
        ordered_numbers = list()
        or_prefix_dec = 0
        or_prefix_bin = to_bin(or_prefix_dec).zfill(MAX_BITS)
        bit_index = 0
        while bit_index < MAX_BITS:
            if or_prefix_bin[bit_index] == '1':
                bit_index += 1
                continue
            (best_dec_pick, best_pick_index) = pick_best(dec_numbers, or_prefix_dec)
            if best_pick_index is not None:
                or_prefix_dec = or_prefix_dec | best_dec_pick
                or_prefix_bin = to_bin(or_prefix_dec).zfill(MAX_BITS)
                ordered_numbers.append(best_dec_pick)
                del dec_numbers[best_pick_index]
            bit_index += 1
        ordered_numbers += list(dec_numbers.values())
        print(' '.join([str(number) for number in ordered_numbers]))
solve()

Solution (Python):
from collections import defaultdict

def to_bin(dec_number):
    return bin(dec_number).replace('0b', '')

def pick_best(dec_numbers, or_prefix_dec):
    best_result = 0
    best_dec_pick = None
    best_pick_index = None
    for (index, dec_number) in dec_numbers.items():
        result = or_prefix_dec | dec_number
        if result > best_result:
            best_result = result
            best_dec_pick = dec_number
            best_pick_index = index
    return (best_dec_pick, best_pick_index)

def solve():
    t = int(input())
    for _ in range(t):
        n = int(input())
        dec_numbers = list(map(int, input().split()))
        dec_numbers = {index: number for (index, number) in enumerate(dec_numbers)}
        max_dec_number = max(dec_numbers.values())
        max_bits = len(to_bin(max_dec_number))
        ordered_numbers = list()
        or_prefix_dec = 0
        or_prefix_bin = to_bin(or_prefix_dec).zfill(max_bits)
        bit_index = 0
        while bit_index < max_bits:
            if or_prefix_bin[bit_index] == '1':
                bit_index += 1
                continue
            (best_dec_pick, best_pick_index) = pick_best(dec_numbers, or_prefix_dec)
            if best_pick_index is not None:
                or_prefix_dec = or_prefix_dec | best_dec_pick
                or_prefix_bin = to_bin(or_prefix_dec).zfill(max_bits)
                ordered_numbers.append(best_dec_pick)
                del dec_numbers[best_pick_index]
            bit_index += 1
            if '0' not in to_bin(or_prefix_dec).zfill(max_bits):
                break
        ordered_numbers += list(dec_numbers.values())
        print(' '.join([str(number) for number in ordered_numbers]))
solve()

Solution (Python):
MAX_BITS = 32

def to_bin(dec_number):
    return bin(dec_number).replace('0b', '')

def pick_best(dec_numbers, or_prefix_dec):
    best_result = 0
    best_dec_pick = None
    best_pick_index = None
    for (index, dec_number) in dec_numbers.items():
        result = or_prefix_dec | dec_number
        if result > best_result:
            best_result = result
            best_dec_pick = dec_number
            best_pick_index = index
    return (best_dec_pick, best_pick_index)

def solve():
    t = int(input())
    for _ in range(t):
        _ = int(input())
        dec_numbers = list(map(int, input().split()))
        dec_numbers = {index: number for (index, number) in enumerate(dec_numbers)}
        ordered_numbers = list()
        or_prefix_dec = 0
        or_prefix_bin = to_bin(or_prefix_dec).zfill(MAX_BITS)
        bit_index = 0
        while bit_index < MAX_BITS:
            if or_prefix_bin[bit_index] == '1':
                bit_index += 1
                continue
            (best_dec_pick, best_pick_index) = pick_best(dec_numbers, or_prefix_dec)
            if best_pick_index is not None:
                or_prefix_dec = or_prefix_dec | best_dec_pick
                or_prefix_bin = to_bin(or_prefix_dec).zfill(MAX_BITS)
                ordered_numbers.append(best_dec_pick)
                del dec_numbers[best_pick_index]
            bit_index += 1
        ordered_numbers += list(dec_numbers.values())
        print(' '.join([str(number) for number in ordered_numbers]))
solve()