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.
Input: num = 5
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
Input: num = 1
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.
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.
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
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
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)