Absolute difference between the count of set bits in N and its reverse - Coding

Given an integer N, the task is to find the absolute difference between the number of set bits present in the number N and in reverse of the number N.

Examples:

Input: N = 13
Output: 2
Explanation:
Binary representation of (13)₁₀ = (1101)₂
Count of set bits = 3
Reverse of 13 is 31
Binary representation of (31)₁₀ = (11111)₂
Count of set bits of reversed number = 5
Absolute Difference is |3 – 5| =2

Input: N = 135
Output: 0
Explanation:
Binary representation of (135)₁₀ = (10000111)₂
Count of set bits =4
Reverse of 135 is 531
Binary representation of (531)₁₀ = (1000010011)₂
Count of set bits of reversed number = 4
Absolute Difference is |4 – 4| = 0

Approach: The main idea is to use the bitset function of the STL library.

Follow the steps below to solve the given problem:

Reverse the digits of the number N and store it in a variable, say revN.
Use the bitset function to count the number of set bits in N.
Return the absolute difference of the number of set bits in N and revN.

Below is the implementation of the above approach:

C++14

// C++ program for
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the
// reverse number of N
int reverse(int N)
{
    // Stores the
    // reverse of N
    int revn = 0;
 
    // Iterate while N exceeds 0
    while (N > 0) {
        // Extract last digit of N
        int b = N % 10;
 
        // Append the last digit
        // of N to revn
        revn = (revn * 10) + b;
 
        // Remove the last digit of N
        N = N / 10;
    }
 
    return revn;
}
 
// Function to find the absolute difference
// between the set bits in N and its reverse
int findAbsoluteDiffernce(int N)
{
    // Store N as bitset
    bitset<64> a(N);
 
    // Stores the reverse of N
    int revn = reverse(N);
 
    // Stores revn as bitset
    bitset<64> b(revn);
 
    // Count set bits in N
    int setBitsInN = a.count();
 
    // Count set bits in revn
    int setBitsInRevN = b.count();
 
    // Return the absolute difference of
    // set bits in N and its reverse
    return abs(setBitsInN - setBitsInRevN);
}
 
// Driver Code
int main()
{
    // Input
    int N = 13;
 
    // Function call to find absolute
    // difference between the count
    // of set bits in N and its reverse
    cout << findAbsoluteDiffernce(N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Function to find the
// reverse number of N
static int reverse(int N)
{
     
    // Stores the
    // reverse of N
    int revn = 0;
 
    // Iterate while N exceeds 0
    while (N > 0)
    {
         
        // Extract last digit of N
        int b = N % 10;
 
        // Append the last digit
        // of N to revn
        revn = (revn * 10) + b;
 
        // Remove the last digit of N
        N = N / 10;
    }
    return revn;
}
 
// Function to find the absolute difference
// between the set bits in N and its reverse
static int findAbsoluteDiffernce(int N)
{
     
    // Count set bits in N
    int setBitsInN = Integer.bitCount(N);
 
    // Stores the reverse of N
    int revn = reverse(N);
 
    // Count set bits in revn
    int setBitsInRevN = Integer.bitCount(revn);
 
    // Return the absolute difference of
    // set bits in N and its reverse
    return Math.abs(setBitsInN - setBitsInRevN);
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Input
    int N = 13;
 
    // Function call to find absolute
    // difference between the count
    // of set bits in N and its reverse
    System.out.println(findAbsoluteDiffernce(N));
}
}
 
// This code is contributed by Kingash

Python3

# Python3 program for
# the above approach
 
# Function to find the
# reverse number of N
def reverse(N):
     
    # Stores the
    # reverse of N
    revn = 0
 
    # Iterate while N exceeds 0
    while (N > 0):
         
        # Extract last digit of N
        b = N % 10
 
        # Append the last digit
        # of N to revn
        revn = (revn * 10) + b
 
        # Remove the last digit of N
        N = N // 10
 
    return revn
 
def countSetBits(n):
     
    count = 0
     
    while n:
        count += (n & 1)
        n >>= 1
         
    return count
   
# Function to find the absolute difference
# between the set bits in N and its reverse
def findAbsoluteDiffernce(N):
     
    # Count set bits in N
    setBitsInN = countSetBits(N)
 
    # Stores the reverse of N
    revn = reverse(N)
 
    # Count set bits in revn
    setBitsInRevN = countSetBits(revn)
 
    # Return the absolute difference of
    # set bits in N and its reverse
    return abs(setBitsInN - setBitsInRevN)
 
# Driver Code
 
# Input
N = 13
 
# Function call to find absolute
# difference between the count
# of set bits in N and its reverse
print(findAbsoluteDiffernce(N))
 
# This code is contributed by rohitsingh07052

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the
// reverse number of N
static int reverse(int N)
{
     
    // Stores the
    // reverse of N
    int revn = 0;
 
    // Iterate while N exceeds 0
    while (N > 0)
    {
         
        // Extract last digit of N
        int b = N % 10;
 
        // Append the last digit
        // of N to revn
        revn = (revn * 10) + b;
 
        // Remove the last digit of N
        N = N / 10;
    }
    return revn;
}
 
// Function to get no of set
// bits in binary representation
// of positive integer n
static int countSetBits(int n)
{
    int count = 0;
     
    while (n > 0) 
    {
        count += n & 1;
        n >>= 1;
    }
    return count;
}
 
// Function to find the absolute difference
// between the set bits in N and its reverse
static int findAbsoluteDiffernce(int N)
{
     
    // Count set bits in N
    int setBitsInN = countSetBits(N);
 
    // Stores the reverse of N
    int revn = reverse(N);
 
    // Count set bits in revn
    int setBitsInRevN = countSetBits(revn);
 
    // Return the absolute difference of
    // set bits in N and its reverse
    return Math.Abs(setBitsInN - setBitsInRevN);
}
 
// Driver Code
public static void Main(string[] args)
{
     
    // Input
    int N = 13;
 
    // Function call to find absolute
    // difference between the count
    // of set bits in N and its reverse
    Console.WriteLine(findAbsoluteDiffernce(N));
}
}
 
// This code is contributed by AnkThon

Javascript

<script>
 
        // Javascript program for the 
        // above approach
 
        // Function to find the
        // reverse number of N
        function reverse( n ) {
        // converting the number to String
            n = n + "";
 
       // splitting the digits into an array
            let arr = n.split("")
 
      // reversing the array
            let revn = arr.reverse()
 
            //joining all in a single string
            return revn.join("");
        }
 
        // Function to find 
        // the absolute difference
        // between the set bits in N 
        // and its reverse
        function findAbsoluteDiffernce(N) {
 
            // Count set bits in N
            let setBitsInN = 
            N.toString(2).split('1').length - 1
             
            // Stores the reverse of N
            let revn = reverse(N);
             
            // Count set bits in revn
            let setBitsInRevN = 
            revn.toString(2).split('1').length - 1
             
            // Return the absolute difference of
            // set bits in N and its reverse
            return Math.abs(setBitsInN - setBitsInRevN);
        }
 
        // Driver Code
 
        // Input
        let N = 13;
 
        // Function call to find absolute
        // difference between the count
        // of set bits in N and its reverse
        document.write(findAbsoluteDiffernce(N))
 
        // This code is contributed by Hritik
         
    </script>

Output:

Time Complexity: O(log N)
Auxiliary Space: O(1)

Reffered: https://www.geeksforgeeks.org

Bit Magic

Related
Print all submasks of a given mask
XOR of all even numbers from a given range
Minimize given flips required to reduce N to 0
Program to find the Nth natural number with exactly two bits set \| Set 2
Calculate Bitwise OR of two integers from their given Bitwise AND and Bitwise XOR values

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	11