Skip to content

3769. Sort Integers by Binary Reflection

Description

You are given an integer array nums.

The binary reflection of a positive integer is defined as the number obtained by reversing the order of its binary digits (ignoring any leading zeros) and interpreting the resulting binary number as a decimal.

Sort the array in ascending order based on the binary reflection of each element. If two different numbers have the same binary reflection, the smaller original number should appear first.

Return the resulting sorted array.

 

Example 1:

Input: nums = [4,5,4]

Output: [4,4,5]

Explanation:

Binary reflections are:

  • 4 -> (binary) 100 -> (reversed) 001 -> 1
  • 5 -> (binary) 101 -> (reversed) 101 -> 5
  • 4 -> (binary) 100 -> (reversed) 001 -> 1
Sorting by the reflected values gives [4, 4, 5].

Example 2:

Input: nums = [3,6,5,8]

Output: [8,3,6,5]

Explanation:

Binary reflections are:

  • 3 -> (binary) 11 -> (reversed) 11 -> 3
  • 6 -> (binary) 110 -> (reversed) 011 -> 3
  • 5 -> (binary) 101 -> (reversed) 101 -> 5
  • 8 -> (binary) 1000 -> (reversed) 0001 -> 1
Sorting by the reflected values gives [8, 3, 6, 5].
Note that 3 and 6 have the same reflection, so we arrange them in increasing order of original value.

 

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 109

Solutions

Solution 1: Custom Sorting

We define a function \(f(x)\) to calculate the binary reflection value of integer \(x\). Specifically, we continuously extract the lowest bit of \(x\) and add it to the end of the result \(y\) until \(x\) becomes \(0\).

Then, we sort the array \(\textit{nums}\) with the sorting key being the tuple \((f(x), x)\) of each element's binary reflection value and original value. This ensures that when two elements have the same binary reflection value, the smaller original value will be placed first.

Finally, we return the sorted array.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\). Where \(n\) is the length of the array \(\textit{nums}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def sortByReflection(self, nums: List[int]) -> List[int]:
        def f(x: int) -> int:
            y = 0
            while x:
                y = y << 1 | (x & 1)
                x >>= 1
            return y

        nums.sort(key=lambda x: (f(x), x))
        return nums

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[] sortByReflection(int[] nums) {
        int n = nums.length;
        Integer[] a = new Integer[n];
        Arrays.setAll(a, i -> nums[i]);

        Arrays.sort(a, (u, v) -> {
            int fu = f(u);
            int fv = f(v);
            if (fu != fv) {
                return Integer.compare(fu, fv);
            }
            return Integer.compare(u, v);
        });

        for (int i = 0; i < n; i++) nums[i] = a[i];
        return nums;
    }

    private int f(int x) {
        int y = 0;
        while (x != 0) {
            y = (y << 1) | (x & 1);
            x >>= 1;
        }
        return y;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> sortByReflection(vector<int>& nums) {
        auto f = [](int x) {
            int y = 0;
            while (x) {
                y = (y << 1) | (x & 1);
                x >>= 1;
            }
            return y;
        };

        sort(nums.begin(), nums.end(), [&](int a, int b) {
            int fa = f(a);
            int fb = f(b);
            if (fa != fb) {
                return fa < fb;
            }
            return a < b;
        });

        return nums;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func sortByReflection(nums []int) []int {
    f := func(x int) int {
        y := 0
        for x != 0 {
            y = (y << 1) | (x & 1)
            x >>= 1
        }
        return y
    }

    sort.Slice(nums, func(i, j int) bool {
        fi := f(nums[i])
        fj := f(nums[j])
        if fi != fj {
            return fi < fj
        }
        return nums[i] < nums[j]
    })

    return nums
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function sortByReflection(nums: number[]): number[] {
    const f = (x: number): number => {
        let y = 0;
        for (; x; x >>= 1) {
            y = (y << 1) | (x & 1);
        }
        return y;
    };

    nums.sort((a, b) => {
        const fa = f(a);
        const fb = f(b);
        if (fa !== fb) {
            return fa - fb;
        }
        return a - b;
    });

    return nums;
}

Comments