Posted on by Kalkicode
Code Recursion

# 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

1. The `bitDifference(n)` function takes an integer `n` 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 if `n` is odd (n % 2 != 0), and then dividing `n` by 2 to right-shift the bits.

2. The `findBitDifference(n)` function calculates the sum of bit differences from 0 to `n` recursively. If `n` is 0, the function returns 0. Otherwise, it calculates the bit difference for the current number `n` using `bitDifference(n)` and adds it to the result of `findBitDifference(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){
int n = 8;
std::cout << "\n Given N : "  <<  n;
std::cout << "\n Result : "  <<  result;
n = 15;
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)
{
// Test Case
int n = 8;
// Display given n
System.out.print("\n Given N : " + n);
// Display calculated result
System.out.print("\n Result : " + result);
n = 15;
// 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 n = 8;
Console.Write("\n Given N : " + n);
Console.Write("\n Result : " + result);
n = 15;
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__":
n = 8
print("Given N : ", n)
print("Result  : ", result)
n = 15
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()
n = 8
print("\n Given N : " ,n)
print("\n Result : " , result)
n = 15
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 n = 8;
console.log("\n Given N : " + n);
console.log("\n Result : " + result);
n = 15;
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:

1. 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.

2. 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)).

## Comment

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.

Categories
Relative Post