Find the sum of bit differences of numbers using recursion
The given problem aims to find the sum of bit differences between all the numbers from 0 to a given integer N. To calculate the bit difference between two numbers, we count the number of different bits in their binary representations. For example, the bit difference between 5 (binary: 0101) and 2 (binary: 0010) is 2.
Problem Statement: We are given a positive integer N. Our task is to find the sum of bit differences of all numbers from 0 to N. To achieve this, we will use recursion to calculate the bit difference of each number separately and then sum up these differences.
Explanation with an Example
Let's take N = 3 as an example to understand how the recursion works.
Step 1: We will find the bit difference for each number from 0 to 3.
- For 0, the binary representation is 0 (0000), and the bit difference is 0.
- For 1, the binary representation is 1 (0001), and the bit difference is 1.
- For 2, the binary representation is 10 (0010), and the bit difference is 1.
- For 3, the binary representation is 11 (0011), and the bit difference is 2.
Step 2: We will sum up the bit differences: 0 + 1 + 1 + 2 = 4.
So, the result for N = 3 is 4.
Pseudocode
Let's write the pseudocode for the algorithm:
function bitDifference(n):
count = 0
while n != 0:
if n % 2 != 0:
count += 1
n = n / 2
return count
function findBitDifference(n):
if n == 0:
return 0
return bitDifference(n) + findBitDifference(n - 1)
Algorithm Explanation
-
The
bitDifference(n)
function takes an integern
and returns the number of set bits (1s) in its binary representation using a while loop. It counts the number of 1s in the binary representation by checking ifn
is odd (n % 2 != 0), and then dividingn
by 2 to right-shift the bits. -
The
findBitDifference(n)
function calculates the sum of bit differences from 0 ton
recursively. Ifn
is 0, the function returns 0. Otherwise, it calculates the bit difference for the current numbern
usingbitDifference(n)
and adds it to the result offindBitDifference(n - 1)
.
Code Solution
#include <stdio.h>
int bitDifference(int n)
{
int count = 0;
while (n != 0)
{
if (n % 2 != 0)
count++;
n = n / 2;
}
return count;
}
// Find the bits difference of given number from 0 to n
int findBitDifference(int n)
{
if (n == 0)
return 0;
return bitDifference(n) + findBitDifference(n - 1);
}
int main()
{
// Test Case
int n = 8;
int result = findBitDifference(n);
printf("Given N: %d\n", n);
printf("Result: %d\n", result);
n = 15;
result = findBitDifference(n);
printf("Given N: %d\n", n);
printf("Result: %d\n", result);
return 0;
}
Output
Given N: 8
Result: 13
Given N: 15
Result: 32
// Include header file
#include <iostream>
class BitDifference
{
public:
int bitDifference(
int n)
{
int count = 0;
while (n != 0)
{
if (n % 2 != 0)
{
count++;
}
n = n / 2;
}
return count;
}
int findBitDifference(
int n)
{
if (n == 0)
{
return 0;
}
return bitDifference(n) + findBitDifference(n - 1);
}
};
int main(int argc, char **argv){
BitDifference *task = new BitDifference();
int n = 8;
int result = task->findBitDifference(n);
std::cout << "\n Given N : " << n;
std::cout << "\n Result : " << result;
n = 15;
result = task->findBitDifference(n);
std::cout << "\n Given N : " << n;
std::cout << "\n Result : " << result;
return 0;
};
Output
Given N : 8
Result : 13
Given N : 15
Result : 32
/*
Java program
Find the sum of bit differences of numbers using recursion
*/
class BitDifference
{
public int bitDifference(int n)
{
int count = 0;
while (n != 0)
{
if (n % 2 != 0) count++;
n = n / 2;
}
return count;
}
public int findBitDifference(int n)
{
if (n == 0) return 0;
return bitDifference(n) + findBitDifference(n - 1);
}
public static void main(String[] args)
{
BitDifference task = new BitDifference();
// Test Case
int n = 8;
int result = task.findBitDifference(n);
// Display given n
System.out.print("\n Given N : " + n);
// Display calculated result
System.out.print("\n Result : " + result);
n = 15;
result = task.findBitDifference(n);
// Display given
System.out.print("\n Given N : " + n);
// Display calculated result
System.out.print("\n Result : " + result);
}
}
Output
Given N : 8
Result : 13
Given N : 15
Result : 32
// Include namespace system
using System;
public class BitDifference
{
public int bitDifference(int n)
{
var count = 0;
while (n != 0)
{
if (n % 2 != 0)
{
count++;
}
n = (int)(n / 2);
}
return count;
}
public int findBitDifference(int n)
{
if (n == 0)
{
return 0;
}
return this.bitDifference(n) + this.findBitDifference(n - 1);
}
public static void Main(string[] args)
{
var task = new BitDifference();
var n = 8;
var result = task.findBitDifference(n);
Console.Write("\n Given N : " + n);
Console.Write("\n Result : " + result);
n = 15;
result = task.findBitDifference(n);
Console.Write("\n Given N : " + n);
Console.Write("\n Result : " + result);
}
}
Output
Given N : 8
Result : 13
Given N : 15
Result : 32
class BitDifference(object) :
def bitDifference(self, n) :
count = 0
while (n != 0) :
if (n % 2 != 0) :
count += 1
n = int(n / 2)
return count
def findBitDifference(self, n) :
if (n == 0) :
return 0
return self.bitDifference(n) + self.findBitDifference(n - 1)
if __name__=="__main__":
task = BitDifference()
n = 8
result = task.findBitDifference(n)
print("Given N : ", n)
print("Result : ", result)
n = 15
result = task.findBitDifference(n)
print("Given N : ", n)
print("Result : ", result)
Output
Given N : 8
Result : 13
Given N : 15
Result : 32
class BitDifference
def bitDifference( n)
count = 0
while (n != 0)
if (n % 2 != 0)
count += 1
end
n = n / 2
end
return count
end
def findBitDifference( n)
if (n == 0)
return 0
end
return self.bitDifference(n) + self.findBitDifference(n - 1)
end
def self.main()
task = BitDifference.new()
n = 8
result = task.findBitDifference(n)
print("\n Given N : " ,n)
print("\n Result : " , result)
n = 15
result = task.findBitDifference(n)
print("\n Given N : ", n)
print("\n Result : ", result)
end
end
BitDifference.main()
Output
Given N : 8
Result : 13
Given N : 15
Result : 32
bitDifference <- function(n) {
count <- 0
while (n != 0) {
if (n %% 2 != 0) {
count <- count + 1
}
n <- as.integer(n / 2)
}
return(count)
}
findBitDifference <- function(n) {
if (n == 0) {
return(0)
}
return(bitDifference(n) + findBitDifference(n - 1))
}
main <- function() {
n <- 8
result <- findBitDifference(n)
cat(paste0("\n Given N : ", n))
cat(paste0("\n Result : ", result))
n <- 15
result <- findBitDifference(n)
cat(paste0("\n Given N : ", n))
cat(paste0("\n Result : ", result))
}
# Call the main function
main()
Output
Given N : 8
Result : 13
Given N : 15
Result : 32
package main
import "fmt"
func bitDifference(n int) int {
var count int = 0
for n != 0 {
if n%2 != 0 {
count++
}
n = n / 2
}
return count
}
func findBitDifference(n int) int {
if n == 0 {
return 0
}
return bitDifference(n) + findBitDifference(n-1)
}
func main() {
var n int = 8
var result int = findBitDifference(n)
fmt.Print("\n Given N : ", n)
fmt.Print("\n Result : ", result)
n = 15
result = findBitDifference(n)
fmt.Print("\n Given N : ", n)
fmt.Print("\n Result : ", result)
}
Output
Given N : 8
Result : 13
Given N : 15
Result : 32
class BitDifference
{
bitDifference(n)
{
var count = 0;
while (n != 0)
{
if (n % 2 != 0)
{
count++;
}
n = parseInt(n / 2);
}
return count;
}
findBitDifference(n)
{
if (n == 0)
{
return 0;
}
return this.bitDifference(n) + this.findBitDifference(n - 1);
}
}
function main()
{
var task = new BitDifference();
var n = 8;
var result = task.findBitDifference(n);
console.log("\n Given N : " + n);
console.log("\n Result : " + result);
n = 15;
result = task.findBitDifference(n);
console.log("\n Given N : " + n);
console.log("\n Result : " + result);
}
main()
Output
Given N : 8
Result : 13
Given N : 15
Result : 32
Resultant Output Explanation
Let's run the code with the provided test cases:
-
For
n = 8
:- Bit Difference for 0:(0000) 0
- Bit Difference for 1:(0001) 1
- Bit Difference for 2:(0010) 1
- Bit Difference for 3:(0011) 2
- Bit Difference for 4:(0100) 1
- Bit Difference for 5:(0101) 2
- Bit Difference for 6:(0110) 2
- Bit Difference for 7:(0111) 3
- Bit Difference for 8:(1000) 1
The sum of all bit differences from 0 to 8 is 13.
-
For
n = 15
:- Bit Difference for 0:(0000) 0
- Bit Difference for 1:(0001) 1
- Bit Difference for 2:(0010) 1
- Bit Difference for 3:(0011) 2
- Bit Difference for 4:(0100) 1
- Bit Difference for 5:(0101) 2
- Bit Difference for 6:(0110) 2
- Bit Difference for 7:(0111) 3
- Bit Difference for 8:(1000) 1
- Bit Difference for 9:(1001) 2
- Bit Difference for 10:(1010) 2
- Bit Difference for 11:(1011) 3
- Bit Difference for 12:(1100) 2
- Bit Difference for 13:(1101) 3
- Bit Difference for 14:(1110) 3
- Bit Difference for 15:(1111) 4
The sum of all bit differences from 0 to 15 is 32.
Time Complexity
The time complexity of the given algorithm is O(N * M), where N is the input integer, and M is the number of bits required to represent the maximum value from 0 to N. In the worst case, M can be the number of bits required to represent N itself (M = log2(N)).
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment