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)10 = (1101)2
Count of set bits = 3
Reverse of 13 is 31
Binary representation of (31)10 = (11111)2
Count of set bits of reversed number = 5
Absolute Difference is |3 – 5| =2Input: N = 135
Output: 0
Explanation:
Binary representation of (135)10 = (10000111)2
Count of set bits =4
Reverse of 135 is 531
Binary representation of (531)10 = (1000010011)2
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 Nint 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 reverseint 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 Codeint 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 approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to find the// reverse number of Nstatic 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 reversestatic 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 Codepublic 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 Ndef 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 revndef 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 reversedef 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# InputN = 13# Function call to find absolute# difference between the count# of set bits in N and its reverseprint(findAbsoluteDiffernce(N))# This code is contributed by rohitsingh07052 |
C#
// C# program for the above approachusing System;class GFG{// Function to find the// reverse number of Nstatic 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 nstatic 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 reversestatic 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 Codepublic 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:
2
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
