Odious Number In C++

In this article, we will discuss the Odious number in C++ with different approaches and examples.

What is the Odious Number?

If a number is positive and the number of set bits in its binary expansion is odd , the number is considered an Odious number . 1 is the first Odious number because it equals (0001) odd number of set bits. Any number that can be written in the powers of two (2^n) will be an Odious Number because those numbers will have 1 followed by zeroes in binary representation. Hence, 1 is an odd number it can be an Odious Number .

The first ten Odious numbers are: 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 us take an example to check whether the given 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):

• ✅ It will call the countOnes function to find the number of set bits in the given integer n.
• ✅ Use a modulo operation with two to determine if the count of set bits is odd.

Complexity Analysis:

Time Complexity:

• ✅ The time complexity to find whether a given number is Odious or not is O(log n ).

Space Complexity:

• ✅ The space complexity to find whether a given number is Odious or not is O(1).

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

Let us take another example to check whether the given number is 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.

IsOdious Role:

• ✅ Call the countOnesBitwise function to find the number of set bits in the input integer n.
• ✅ Use a modulo operation with two to determine if the count of set bits is odd.

Complexity Analysis:

Time Complexity:

• ✅ The time complexity to find whether a given number is Odious or not is O(log n).

Space Complexity:

• ✅ The space complexity to find whether a given number is Odious or not is O(1).