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){
	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:

  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.

New Comment





Categories
Relative Post