How do we check if a given number is an odious number?
Overview
An odious number is a positive number whose count of set bits in its binary form is odd. All powers of 2 are odious numbers, as the number of set bits in them is 1.
For example, 7 is an odious number because the number of set bits in it is 3.
Given a number n, find whether it is an odious number or not.
Example 1:
- Input: n = 5
- Output: 5 is not an odious number.
Example 1:
- Input: n = 2
- Output: 2 is an odious number.
Solution
The solution is quite straightforward. The steps in figuring out the solution are as follows:
- Find the count of set bits in the given number.
- Check whether the result from step 1 is odd.
For step 1, refer to the How to find the number of set bits in an integer Answer.
For step 2, refer to the How to use bitwise operations to check if a number is even or odd Answer.
Example
def countSetBits(n):count = 0while n:n = n & (n - 1)count+=1return countdef isOdd(n):return (n & 1) == 1n = 16set_bit_count = countSetBits(n)if isOdd(set_bit_count):print(n, "is an Odious number")else:print(n, "is not an Odious number")
Explanation
- Lines 1–6: We define a function called
countSetBitsthat calculates the number of set bits in a given number. - Lines 8–9: We define a function called
isOddthat states whether a given number is an odd number or not. - Line 11: We define the number to be checked as
n. - Line 12: We invoke the
countSetBits()function withnas the number and we get the number of set bits inn. - Lines 13–16: We check whether the result we got in line 18 is an odd number or not by invoking the
isOddfunction. Then, we print the result to the console.