Data Modelling & AI Data Structure & Algorithm

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

23 June 2025

0

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)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

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

C++14

Java

Python3

C#

Javascript

Smarter Retrieval for RAG: Late Chunking with Jina Embeddings v2 and Milvus

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US