Sort Integers by The Number of 1 Bits

🏠 ⬅️ ➡️

You are given an integer array arr. Sort the integers in the array in ascending order by the number of 1's in their binary representation and in case of two or more integers have the same number of 1's you have to sort them in ascending order.

Return the array after sorting it.

Example 1:

Input: arr = [0,1,2,3,4,5,6,7,8] Output: [0,1,2,4,8,3,5,6,7] Explantion: [0] is the only integer with 0 bits. [1,2,4,8] all have 1 bit. [3,5,6] have 2 bits. [7] has 3 bits. The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Example 2:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1] Output: [1,2,4,8,16,32,64,128,256,512,1024] Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

Constraints:

  • 1 <= arr.length <= 500
  • 0 <= arr[i] <= 104
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 9
    integer :: arr(n) = reshape([0, 1, 2, 3, 4, 5, 6, 7, 8], shape(arr))
    integer :: i, j, tmp

    call sort_by_bits(arr)

    do i = 1, size(arr)
        write(*, '(I0)', advance='no') arr(i)
    end do
    write(*,*)

contains

subroutine sort_by_bits(arr)
    implicit none
    integer, intent(inout) :: arr(:)
    integer :: i, j, tmp

    do i = 1, size(arr) - 1
        do j = i + 1, size(arr)
            if (count_bits(arr(i)) < count_bits(arr(j))) then
                tmp = arr(i)
                arr(i) = arr(j)
                arr(j) = tmp
            else if (count_bits(arr(i)) == count_bits(arr(j)) .and. arr(i) > arr(j)) then
                tmp = arr(i)
                arr(i) = arr(j)
                arr(j) = tmp
            end if
        end do
    end do
end subroutine sort_by_bits

function count_bits(x) result(res)
    implicit none
    integer, value :: x
    integer :: res

    res = 0
    do while (x /= 0)
        res = res + 1
        x = x - 2 * (mod(x, 2))
    end do
end function count_bits

end program main
❌ Compiled
❌ Executed
❌ Correct 
module sort_by_bits
    implicit none
    private
    public :: sort_by_bits
contains
    function sort_by_bits(arr) result(sorted_arr)
        integer, intent(in) :: arr(:)
        integer :: sorted_arr(size(arr))
        integer :: i, j, temp
        logical :: swapped

        do
            swapped = .false.
            do i = 1, size(arr) - 1
                if (count_bits(arr(i)) > count_bits(arr(i + 1))) then
                    temp = arr(i)
                    arr(i) = arr(i + 1)
                    arr(i + 1) = temp
                    swapped = .true.
                end if
            end do
            if (.not. swapped) exit
        end do

        sorted_arr = arr
    end function sort_by_bits

    function count_bits(n) result(count)
        integer, intent(in) :: n
        integer :: count
        integer :: i

        count = 0
        do i = n, 1, -1
            if (mod(n, 2) == 1) then
                count = count + 1
            end if
            n = n / 2
        end do
    end function count_bits
end module sort_by_bits

program test_sort_by_bits
    use sort_by_bits
    implicit none
    integer, parameter :: arr1(9) = [0, 1, 2, 3, 4, 5, 6, 7, 8]
    integer, parameter :: arr2(11) = [1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
    integer :: arr(9)

    arr = arr1
    write (*, '(A)') 'Example 1:'
    write (*, '(A)') 'Input:  ' // to_string(arr)
    write (*, '(A)') 'Output: ' // to_string(sort_by_bits(arr))
    write (*, *)

    arr = arr2
    write (*, '(A)') 'Example 2:'
    write (*, '(A)') 'Input:  ' // to_string(arr)
    write (*, '(A)') 'Output: ' // to_string(sort_by_bits(arr))
    write (*, *)
contains
    function to_string(arr) result(str)
        integer, intent(in) :: arr(:)
        character(len=:), allocatable :: str
        integer :: i

        allocate(character(len=size(arr)*10) :: str)
        do i = 1, size(arr)
            write (str(10*(i-1)+1:10*i), '(I10)') arr(i)
        end do
    end function to_string
end program test_sort_by_bits
🌐 Data from online sources 
def min_moves_to_palindrome(s: str) -> int:
    moves = 0
    s = list(s)
    left, right = 0, len(s) - 1

    while left < right:
        if s[left] != s[right]:
            temp_right = right

            while s[left] != s[temp_right]:
                temp_right -= 1
            s.insert(right, s.pop(temp_right))
            moves += right - temp_right
        left += 1
        right -= 1

    return moves
  1. Initialize variables moves to store the total number of moves, and left and right pointers for both ends of string s.
  2. Iterate until the left pointer is less than right. a. If the characters at the left and right pointers are not equal, find the position of the left pointer character in the remaining right section of the string. b. Swap the characters found in the right section with the character at 'right' position. c. Increment the number of moves by the distance between the right and the swap position.
  3. Increment the left pointer and decrement the right pointer after each iteration.
  4. Finally, return the total number of moves.
🌐 Data from online sources 
#include <string>
using namespace std;

int min_moves_to_palindrome(string s) {
    int moves = 0;
    int left = 0, right = s.length() - 1;

    while (left < right) {
        if (s[left] != s[right]) {
            int temp_right = right;

            while (s[left] != s[temp_right]) {
                temp_right--;
            }
            s.erase(s.begin() + temp_right);
            s.insert(s.begin() + right, s[left]);
            moves += right - temp_right;
        }
        left++;
        right--;
    }

    return moves;
}
  1. Initialize variables moves to store the total number of moves, and left and right pointers for both ends of string s.
  2. Iterate until the left pointer is less than right. a. If the characters at the left and right pointers are not equal, find the position of the left pointer character in the remaining right section of the string. b. Swap the characters found in the right section with the character at 'right' position. c. Increment the number of moves by the distance between the right and the swap position.
  3. Increment the left pointer and decrement the right pointer after each iteration.
  4. Finally, return the total number of moves.