Odious Number In C++

In this guide, we will explore the concept of an Odious number in C++ using various strategies and illustrations.

What is the Odious Number?

If a number is positive and has an odd number of set bits in its binary form, it is classified as an Odious number. The first Odious number is 1 since it contains an odd number of set bits in its binary representation (0001). Any number that can be expressed as a power of two (2^n) will also be an Odious number due to the binary representation consisting of a leading 1 followed by zeroes. Therefore, since 1 is an odd number, it qualifies as an Odious number.

The initial ten Odious integers consist of: 1, 2, 4, 7, 10, 11, 13, 14, 16, 19.

For Example:

Input:

Output:

• ✅ Odious Number.
• ✅ Binary Expansion: 1110
• ✅ Here there are 3 set bits, and 3 is an odd number.
• ✅ Hence, 14 is an Odious number.

Input:

Output:

• ✅ Odious Number.
• ✅ Binary Expansion: 11001
• ✅ Here there are 3 set bits, and 3 is an odd number.
• ✅ Hence, 25 is an Odious number.

Input:

Output:

• ✅ Not an Odious Number.
• ✅ Binary Expansion: 100000 (2^5).
• ✅ Here there is only one set bit, and 1 is an odd number.
• ✅ 32 is an Odious number.

Approach 1: Counting for several ones in binary representation.

Let's consider an example to determine if a provided number is an Odious number or not:

#include<iostream>
using namespace std;
// Function to count the number of set bits (1s) in a number
int countOnes(int n) {
    int count = 0;
    while (n >=1) 
{
if(n%2==1)
 count++;
        n /= 2;
    }
    return count;
}
// Function to check if a number is odious
bool isOdious(int n) {
    int ones = countOnes(n);
    return ones % 2 == 1;
}
int main() {
    int number;
    cout << "Enter a non-negative integer: ";
    cin >> number;
    if (isOdious(number))
        cout << number << " is an odious number." << endl;
    else
        cout << number << " is not an odious number." << endl;
    return 0;
}

Output:

Explanation:

Function definition:

• ✅ countOnes(int n): This function determines how many set bits (1s) an integer has in its binary representation.
• ✅ isOdious(int n): This function determines whether an integer's binary representation's set bit count is odd.
• ✅ This function determines how many set bits (1s) an integer has in its binary representation.
• ✅ This function determines whether an integer's binary representation's set bit count is odd.

countOnes(int n):

• ✅ First, set a variable's count to zero.
• ✅ Next, divide the input number n by two repeatedly, going through each bit in turn.
• ✅ If there is a set bit indicated by the remainder of n divided by 2, increments count.
• ✅ Gives back the total number of set bits.

IsOdious (int n):

• ✅ This function invokes the countOnes method to calculate the total set bits in the provided integer n.
• ✅ Check for oddness by performing a modulo operation with two on the count of set bits.

Complexity Analysis:

Time Complexity:

The computational complexity for determining if a specified number is Odious or not is O(log n).

Space Efficiency:

The space complexity for determining if a specified number is Odious or not remains constant at O(1).

Approach 2: Using bitwise operations to count the set bits.

Let's consider another instance to verify if the provided number qualifies as an Odious number or not:

#include<iostream>
using namespace std;
// Function to count the number of set bits (1s) in a number using bitwise operations
int countOnesBitwise(int n) {
    int count = 0;
while(n>=1)
{
        count += n & 1;
        n >>= 1;
    }
    return count;
}
// Function to check if a number is odious
bool isOdious(int n) {
    int ones = countOnesBitwise(n);
    return ones % 2 == 1;
}
int main() {
    int number;
    cout << "Enter a non-negative integer: ";
    cin >> number;
    if (isOdious(number))
        cout << number << " is an odious number." << endl;
    else
        cout << number << " is not an odious number." << endl;   
    return 0;
}

Output:

Explanation:

Function Definition:

• ✅ countOnesBitwise(int n): This function uses bitwise operations to determine how many set bits (1s) are present in the binary representation of a given integer.
• ✅ isOdious(int n):
• ✅ This function determines whether an integer's binary representation's set bit count is odd .
• ✅ This function uses bitwise operations to determine how many set bits (1s) are present in the binary representation of a given integer.

countOnesBitwise:

• ✅ First, set a variable's count to zero.
• ✅ Next, the bitwise AND operation with 1 is used to iterate through each bit of the input number n.
• ✅ If a set bit is indicated by the bitwise AND operation and the result is non-zero, the increments count.
• ✅ In order to consider the next bit, right shifts n by one bit each iteration.
• ✅ Gives back the total number of set bits.

Invoke the countOnesBitwise function to calculate the total number of set bits in the given integer n.

Apply a modulo operation with two to ascertain whether the count of set bits is an odd number.

Complexity Analysis:

Time Complexity:

Determining if a specific number is Odious or not has a time complexity of O(log n).

Space Efficiency:

The space complexity for determining if a specified number is Odious or not is constant, denoted as O(1).