Number of values of b such that a = b + (a^b)

0 0 5 minutes read

Given an integer $a$ . Find the number of solutions of $b$ which satisfies the equation:

a = b + (a^b)

Examples:

Input: a = 4 
Output: 2
The only values of b are 0 and 4 itself.

Input: a = 3 
Output: 4

A naive solution is to iterate from 0 to $a$ and count the number of values that satisfies the given equation. We need to traverse only till $a$ since any value greater than $a$ will give the XOR value > $a$ , hence cannot satisfy the equation.

Below is the implementation of the above approach:

C++

// C++ program to find the number of values
// of b such that a = b + (a^b)
#include <bits/stdc++.h>
using namespace std;
 
// function to return the number of solutions
int countSolutions(int a)
{
    int count = 0;
 
    // check for every possible value
    for (int i = 0; i <= a; i++) {
        if (a == (i + (a ^ i)))
            count++;
    }
 
    return count;
}
 
// Driver Code
int main()
{
    int a = 3;
    cout << countSolutions(a);
}

Java

// Java program to find the number of values
// of b such that a = b + (a^b)
 
import java.io.*;
 
class GFG {
 
 
// function to return the number of solutions
 static int countSolutions(int a)
{
    int count = 0;
 
    // check for every possible value
    for (int i = 0; i <= a; i++) {
        if (a == (i + (a ^ i)))
            count++;
    }
 
    return count;
}
 
// Driver Code
 
 
    public static void main (String[] args) {
        int a = 3;
    System.out.println( countSolutions(a));
    }
}
// This code is contributed by inder_verma

Python3

# Python 3 program to find 
# the number of values of b
# such that a = b + (a^b)
 
# function to return the 
# number of solutions
def countSolutions(a):
 
    count = 0
 
    # check for every possible value
    for i in range(a + 1):
        if (a == (i + (a ^ i))):
            count += 1
 
    return count
 
# Driver Code
if __name__ == "__main__":
    a = 3
    print(countSolutions(a))
 
# This code is contributed
# by ChitraNayal

C#

// C# program to find the number of 
// values of b such that a = b + (a^b)
using System;
 
class GFG 
{
 
// function to return the
// number of solutions
static int countSolutions(int a)
{
    int count = 0;
 
    // check for every possible value
    for (int i = 0; i <= a; i++) 
    {
        if (a == (i + (a ^ i)))
            count++;
    }
 
    return count;
}
 
// Driver Code
public static void Main () 
{
    int a = 3;
    Console.WriteLine(countSolutions(a));
}
}
 
// This code is contributed by inder_verma

PHP

<?php
// PHP program to find the number of 
// values of b such that a = b + (a^b)
 
// function to return the 
// number of solutions
function countSolutions($a)
{
    $count = 0;
 
    // check for every possible value
    for ($i = 0; $i <= $a; $i++) 
    {
        if ($a == ($i + ($a ^ $i)))
            $count++;
    }
 
    return $count;
}
 
// Driver Code
$a = 3;
echo countSolutions($a);
 
// This code is contributed 
// by inder_verma
?>

Javascript

<script>
 
// Javascript program to find the number of values
// of b such that a = b + (a^b)
 
// function to return the number of solutions
function countSolutions(a)
{
    let count = 0;
 
    // check for every possible value
    for (let i = 0; i <= a; i++) {
        if (a == (i + (a ^ i)))
            count++;
    }
 
    return count;
}
 
// Driver Code
let a = 3;
document.write(countSolutions(a));
 
</script>

Output:

Time Complexity: O(a), since there runs a loop for a times.
Auxiliary Space: O(1), since no extra space has been taken.

An Efficient Approach is to observe a pattern of answers when we write the possible solutions for different values of $a$ . Only the set bits are used to determine the number of possible answers. The answer to the problem will always be 2^(number of set bits) which can be determined by observation.

Below is the implementation of the above approach:

C++

// C++ program to find the number of values
// of b such that a = b + (a^b)
#include <bits/stdc++.h>
using namespace std;
 
// function to return the number of solutions
int countSolutions(int a)
{
    int count = __builtin_popcount(a);
 
    count = pow(2, count);
    return count;
}
 
// Driver Code
int main()
{
    int a = 3;
    cout << countSolutions(a);
}

Java

// Java program to find the number of values
// of b such that a = b + (a^b)
import java.io.*;
class GFG
{
  
    // function to return the number of solutions
    static int countSolutions(int a)
    {
        int count = Integer.bitCount(a);
      
        count =(int) Math.pow(2, count);
        return count;
    }
      
    // Driver Code
        public static void main (String[] args) 
    {
        int a = 3;
        System.out.println(countSolutions(a));
    }
}
// This code is contributed by Raj

Python3

# Python3 program to find the number 
# of values of b such that a = b + (a^b) 
 
# function to return the number 
# of solutions 
def countSolutions(a): 
 
    count = bin(a).count('1') 
    return 2 ** count 
 
# Driver Code 
if __name__ == "__main__":
 
    a = 3
    print(countSolutions(a)) 
 
# This code is contributed by
# Rituraj Jain

C#

// C# program to find the number of 
// values of b such that a = b + (a^b)
class GFG
{
 
// function to return the number 
// of solutions
static int countSolutions(int a)
{
    int count = bitCount(a);
 
    count =(int) System.Math.Pow(2, count);
    return count;
}
 
static int bitCount(int n)
{
    int count = 0;
    while (n != 0)
    {
        count++;
        n &= (n - 1);
    }
    return count;
}
 
// Driver Code
public static void Main() 
{
    int a = 3;
    System.Console.WriteLine(countSolutions(a));
}
}
 
// This code is contributed by mits

PHP

<?php
// PHP program to find the number of 
// values of b such that a = b + (a^b)
 
// function to return the number 
// of solutions
function countSolutions($a)
{
    $count = bitCount($a);
 
    $count = (int)pow(2, $count);
    return $count;
}
 
function bitCount($n)
{
    $count = 0;
    while ($n != 0)
    {
        $count++;
        $n &= ($n - 1);
    }
    return $count;
}
 
// Driver Code
$a = 3;
echo (countSolutions($a));
 
// This code is contributed by ajit
?>

Javascript

<script>
 
// Javascript program to find the number
// of values of b such that a = b + (a^b)
function bitCount(n)
{
    let count = 0;
    while (n != 0)
    {
        count++;
        n &= (n - 1);
    }
    return count;
}
 
// Function to return the number of solutions
function countSolutions(a)
{
    let count = bitCount(a);
 
    count = Math.pow(2, count);
    return count;
}
 
// Driver Code
let a = 3;
 
document.write(countSolutions(a));
 
// This code is contributed by subhammahato348
 
</script>

Output:

Time Complexity: O(log N) since inbuilt pow function has been used which takes logarithmic time.
Auxiliary Space: O(1), since no extra space has been taken.

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 zambiatek!