Complement of Base 10 Integer

🏠 ⬅️ ➡️

The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.

  • For example, The integer 5 is "101 " in binary and its complement is "010 " which is the integer 2.

Given an integer n, return its complement.

Example 1:

Input: n = 5 Output: 2 Explanation: 5 is "101 " in binary, with complement "010 " in binary, which is 2 in base-10.

Example 2:

Input: n = 7 Output: 0 Explanation: 7 is "111 " in binary, with complement "000 " in binary, which is 0 in base-10.

Example 3:

Input: n = 10 Output: 5 Explanation: 10 is "1010 " in binary, with complement "0101 " in binary, which is 5 in base-10.

Constraints:

  • 0 <= n < 109

Note: This question is the same as 476: https://leetcode.com/problems/number-complement/

Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    !! Solves the problem described in the comment block
    implicit none

    integer :: n, complement

    ! Examples
    n = 5
    write (*, '(A, I0)') 'Complement of ', n, ' is ', complement(n)
    n = 7
    write (*, '(A, I0)') 'Complement of ', n, ' is ', complement(n)
    n = 10
    write (*, '(A, I0)') 'Complement of ', n, ' is ', complement(n)

contains

    function complement(n) result(res)
        !! Returns the complement of an integer
        implicit none
        integer, intent(in) :: n
        integer :: res

        res = iand(not(n), 1_8)
    end function complement

end program main
❌ Compiled
❌ Executed
❌ Correct 
!include(header.inc)

program complement

implicit none

integer :: n, complement

! Read input
read(*,*) n

! Calculate complement
complement = 0
do while (n > 0)
    if (mod(n, 2) == 0) then
        complement = complement + 1
    end if
    n = n / 2
end do

! Output result
write(*,*) complement

end program complement

!include(footer.inc)
🌐 Data from online sources 
def pancakeSort(arr):
    flips = []
    for size in range(len(arr), 1, -1):
        maxIdx = arr.index(max(arr[:size]))
        flips.extend([maxIdx + 1, size])
        arr[:maxIdx + 1] = reversed(arr[:maxIdx + 1])
        arr[:size] = reversed(arr[:size])
    return flips

The algorithm be: 1. Iterate over the array from the last element to the first. 2. During each iteration, find the index of the maximum element in the unsorted part of the array. 3. Perform a pancake flip at the maximum element index, to move it to the beginning of the array. 4. Perform a pancake flip for the whole unsorted part of the array to place the maximum element at its correct position. 5. Add the flip positions in the list of flips. 6. The algorithm ends when the array is completely sorted.

This guarantees that the array will be sorted within 2 * arr.length flips.

🌐 Data from online sources 
#include <vector>
#include <algorithm>
using namespace std;

vector<int> pancakeSort(vector<int>& arr) {
    vector<int> flips;
    for (int size = arr.size(); size > 1; --size) {
        int maxIdx = max_element(arr.begin(), arr.begin() + size) - arr.begin();
        flips.push_back(maxIdx + 1);
        flips.push_back(size);
        reverse(arr.begin(), arr.begin() + maxIdx + 1);
        reverse(arr.begin(), arr.begin() + size);
    }
    return flips;
}

The algorithm be: 1. Iterate over the array from the last element to the first. 2. During each iteration, find the index of the maximum element in the unsorted part of the array. 3. Perform a pancake flip at the maximum element index, to move it to the beginning of the array. 4. Perform a pancake flip for the whole unsorted part of the array to place the maximum element at its correct position. 5. Add the flip positions in the list of flips. 6. The algorithm ends when the array is completely sorted.

This guarantees that the array will be sorted within 2 * arr.length flips.