Recursive Thinking approach (python)

yusufadel

YusufAdel

Posted on April 8, 2021

Recursive Thinking approach (python)

Here's the code snippet with improved markdown formatting and readability:


A recursive definition is one which uses the word or concept being defined in the definition itself. Before applying recursion to programming, it is best to practice thinking recursively. Here I'm gonna to show you a good example for clarifying the purpose in detail.

Problem Statement:

The problem is finding the complement number of a binary format.

Example 1:

Input:

num = 5
Enter fullscreen mode Exit fullscreen mode

Output:

2
Enter fullscreen mode Exit fullscreen mode

Explanation:
The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Example 2:

Input:

num = 1
Enter fullscreen mode Exit fullscreen mode

Output:

0
Enter fullscreen mode Exit fullscreen mode

Explanation:
The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

Constraints:

  • The given integer num is guaranteed to fit within the range of a 32-bit signed integer.
  • num >= 1
  • You could assume no leading zero bit in the integer’s binary representation.

Python Solution:

class Solution:
    def findComplement(self, num: int) -> int:
        # Convert num to binary format
        binary_num = bin(num)[2:]  # '101'

        # Get complement by replacing every '0' with '1'
        new_binary_num = binary_num.replace('0', '1')  # '111'

        # Convert binary complement to integer
        int_num = int(new_binary_num, 2)  # 7

        # Calculate the difference to get the complement
        difference = int_num - num  # 7 - 5 = 2

        return difference
Enter fullscreen mode Exit fullscreen mode

Explanation:

  • Formatting the integer input to a proper binary to get processed, slicing it with [2:] to avoid the 0b prefix as the output.
  • To get the complement, we replace every '0' with '1'.
  • We then turn it into the integer format again using the additional int() argument base=2.
  • Finally, we calculate the difference, which represents the complement of the binary sequence.

Additional resources:
For curious readers


💖 💪 🙅 🚩
yusufadel
YusufAdel

Posted on April 8, 2021

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

Recursive Thinking approach (python)
programming Recursive Thinking approach (python)

April 8, 2021