Wednesday, November 13, 2024
Google search engine
HomeData Modelling & AICount of values of x <= n for which (n XOR x)...

Count of values of x <= n for which (n XOR x) = (n – x)

Given an integer n, the task is to find the number of possible values of 0 ? x ? n which satisfy n XOR x = n – x.

Examples: 

Input: n = 5 
Output:
Following values of x satisfy the equation 
5 XOR 0 = 5 – 0 = 5 
5 XOR 1 = 5 – 1 = 4 
5 XOR 4 = 5 – 4 = 1 
5 XOR 5 = 5 – 5 = 0

Input: n = 2 
Output:
 

Naive approach: The easy approach is to check for all values from 0 to n (both inclusive) and finding whether they satisfy the equation. The below code implements this approach:

Below is the implementation of the above approach:  

C++




// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to return the count of
// valid values of x
static int countX(int n)
{
    int count = 0;
 
    for (int i = 0; i <= n; i++)
    {
 
        // If n - x = n XOR x
        if (n - i == (n ^ i))
                count++;
    }
 
        // Return the required count;
        return count;
}
 
// Driver code
int main()
{
    int n = 5;
    int answer = countX(n);
    cout << answer;
}
 
// This code is contributed by
// Shivi_Aggarwal


Java




// Java implementation of the approach
public class GFG {
 
    // Function to return the count of
    // valid values of x
    static int countX(int n)
    {
        int count = 0;
 
        for (int i = 0; i <= n; i++) {
 
            // If n - x = n XOR x
            if (n - i == (n ^ i))
                count++;
        }
 
        // Return the required count;
        return count;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int n = 5;
        int answer = countX(n);
        System.out.println(answer);
    }
}


Python3




# Python3 implementation of the approach
import math as mt
 
# Function to return the count of
# valid values of x
def countX(n):
    count = 0
 
    for i in range(n + 1):
 
        if n - i == (n ^ i):
            count += 1
 
    return count
 
# Driver Code
if __name__ == '__main__':
    n = 5
    answer = countX(n)
    print(answer)
 
# This code is contributed by
# Mohit kumar 29


C#




// C# implementation of the above approach
using System;
 
class GFG
{
 
    // Function to return the count of
    // valid values of x
    static int countX(int n)
    {
        int count = 0;
 
        for (int i = 0; i <= n; i++)
        {
 
            // If n - x = n XOR x
            if (n - i == (n ^ i))
                count++;
        }
 
        // Return the required count;
        return count;
    }
 
    // Driver code
    public static void Main()
    {
        int n = 5;
        int answer = countX(n);
        Console.WriteLine(answer);
    }
}
 
// This code is contributed by Ryuga


PHP




<?php
// PHP implementation of the approach
 
// Function to return the count of
// valid values of x
function countX($n)
{
    $count = 0;
 
    for ($i = 0; $i <= $n; $i++)
    {
 
        // If n - x = n XOR x
        if ($n - $i == ($n ^ $i))
            $count++;
    }
 
    // Return the required count;
    return $count;
}
 
// Driver code
$n = 5;
$answer = countX($n);
echo($answer);
 
// This code is Contributed
// by Mukul Singh.
?>


Javascript




<script>
 
// Javascript implementation of the approach
 
// Function to return the count of
// valid values of x
function countX(n)
{
    let count = 0;
 
    for (let i = 0; i <= n; i++)
    {
 
        // If n - x = n XOR x
        if (n - i == (n ^ i))
                count++;
    }
 
        // Return the required count;
        return count;
}
 
// Driver code
    let n = 5;
    let answer = countX(n);
    document.write(answer);
 
</script>


Output: 

4

 

Time complexity: O(N)
Auxiliary Space: O(1)

Efficient Approach: Convert n to its binary representation. Now, for every 1 in the binary string whether we subtract 1 or 0 from it, it will be equivalent to XOR of 1 with 0 or 1 i.e. 
(1 – 1) = (1 XOR 1) = 0 
(1 – 0) = (1 XOR 0) = 1 
But 0 doesn’t satisfy this condition. So, we only need to consider all the ones in the binary representation of n. Now, for every 1 there are two possibilities, either 0 or 1. Thus if we have m number of 1’s in n then our solution would be 2m.

Below is the implementation of the above approach:  

C++




// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to return the count of
// valid values of x
int countX(int n)
{
    // Convert n into binary String
    string binary = bitset<8>(n).to_string();
     
    // To store the count of 1s
    int count = 0;
    for (int i = 0; i < binary.length(); i++)
    {
        // If current bit is 1
        if (binary.at(i) == '1')
            count++;
    }
     
    // Calculating answer
    int answer = (int)pow(2, count);
    return answer;
}
 
// Driver code
int main()
{
    int n = 5;
    int answer = countX(n);
    cout << (answer);
}
 
// This code is contributed by Rajput-Ji


Java




// Java implementation of the approach
public class GFG {
 
    // Function to return the count of
    // valid values of x
    static int countX(int n)
    {
        // Convert n into binary String
        String binary = Integer.toBinaryString(n);
 
        // To store the count of 1s
        int count = 0;
 
        for (int i = 0; i < binary.length(); i++) {
 
            // If current bit is 1
            if (binary.charAt(i) == '1')
                count++;
        }
 
        // Calculating answer
        int answer = (int)Math.pow(2, count);
        return answer;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int n = 5;
        int answer = countX(n);
        System.out.println(answer);
    }
}


Python3




# Python3 implementation of the approach
 
# Function to return the count of
# valid values of x
def countX(n):
 
    # Convert n into binary String
    binary = "{0:b}".format(n)
 
    # To store the count of 1s
    count = 0
 
    for i in range(len(binary)):
 
        # If current bit is 1
        if (binary[i] == '1'):
            count += 1
 
    # Calculating answer
    answer = int(pow(2, count))
    return answer
 
# Driver code
if __name__ == "__main__":
     
    n = 5
    answer = countX(n)
    print(answer)
 
# This code is contributed by ita_c


C#




// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the count of
// valid values of x
static int countX(int n)
{
    // Convert n into binary String
    string binary = Convert.ToString(n, 2);
 
    // To store the count of 1s
    int count = 0;
 
    for (int i = 0; i < binary.Length; i++)
    {
 
        // If current bit is 1
        if (binary[i] == '1')
            count++;
    }
 
    // Calculating answer
    int answer = (int)Math.Pow(2, count);
    return answer;
}
 
// Driver code
public static void Main()
{
    int n = 5;
    int answer = countX(n);
    Console.WriteLine(answer);
}
}
 
// This code is contributed
// by Akanksha Rai


Javascript




<script>
 
// Javascript implementation of the approach
 
// Function to return the count of
// valid values of x
function countX(n)
{
     
    // Convert n into binary String
    let binary = (n >>> 0).toString(2);
 
    // To store the count of 1s
    let count = 0;
 
    for(let i = 0; i < binary.length; i++)
    {
         
        // If current bit is 1
        if (binary[i] == '1')
            count++;
    }
 
    // Calculating answer
    let answer = Math.floor(Math.pow(2, count));
    return answer;
}
 
// Driver code
let n = 5;
let answer = countX(n);
 
document.write(answer);
     
// This code is contributed by avanitrachhadiya2155
 
</script>


Output: 

4

 

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!

RELATED ARTICLES

Most Popular

Recent Comments