DEV Community

Cover image for Recursive Thinking approach (python)
YusufAdel
YusufAdel

Posted on

Recursive Thinking approach (python)

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 detailed .

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

**Example 1:

Input: num = 5
Output: 2
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
Output: 0
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.
Enter fullscreen mode Exit fullscreen mode
class Solution:
    def findComplement(self, num: int) -> int:
        binary_num = bin(num)[2:] # >>> '101'
        new_binary_num = binary_num.replace('0','1') #>>>'111'
        int_num = int(new_binary_num, 2) #>>>7
        difference = int_num - num # >>>7-5 = 2
        return difference    
Enter fullscreen mode Exit fullscreen mode

At the begging you are in front of two choices, the efficiency (run time) ,and the memory management

Here we have chose the memory, however, run time won't be that bad too! in a worst case it would be O(n).

explaining python code:
1- formatting the integer input to proper binary to get processed slicing it with [2:] to avoid the 0b prefix
as the output
bin(5) = 0b101


2-to get the complement we can get the maximum value out of the binary sequence by replacing every '0' with '1'

3-turn it to the integer format again using the additional int() argument base=...

int('101', 2) = 5 or we can do that int('0b101', 2)

4- get the difference which will represent the complement of the binary sequence

additional resource to view the idea from another perspective
For curios readers

Top comments (0)