Given an integer N, the task is to count the number of integers (say x) in the range [0, 2N−1] such that x⊕(x+1) = (x+2)⊕(x+3). [where ⊕ represents bitwise Xor]
Examples:
Input: N = 1
Output: 1
Explanation: Only 0 is the valid x, as, 0 ⊕ 1 = 2 ⊕ 3 = 1Input: N = 3
Output: 4
Naive Approach: The simple approach to solve the given problem is to generate all possible values of x in the range [0, 2N−1] and check if they satisfy the given criteria i.e x⊕(x+1) = (x+2)⊕(x+3).
Follow the steps mentioned below to implement the idea:
- Iterate from i = 0 to N.
- Check if (i ⊕ (i+1)) = ((i+2) ⊕ (i+3))
- If the condition is satisfied increment the count of such numbers.
- Return the final count as the answer.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find number of integers// satisfying the conditionint countOfvalues(int N){ // Stores the resultant count of pairs int count = 0; for (int i = 0; i < (1 << N); i++) { // Iterate over the range if ((i ^ (i + 1)) == ((i + 2) ^ (i + 3))) count += 1; } return count;}// Driver Codeint main(){ int N = 3; // Function call cout << countOfvalues(N); return 0;}// This code is contributed by Rohit Pradhan |
Java
// Java code to implement the approachclass GFG { // Function to find number of integers // satisfying the condition public static int countOfvalues(int N) { // Stores the resultant count of pairs int count = 0; for (int i = 0; i < (1 << N); i++) { // Iterate over the range if ((i ^ (i + 1)) == ((i + 2) ^ (i + 3))) count += 1; } return count; } // Driver code public static void main(String[] args) { int N = 3; // Function call System.out.println(countOfvalues(N)); }}// This code is contributed by phasing17 |
Python3
# Python3 code to implement the approach# Function to find number of integers # satisfying the conditiondef countOfvalues(N): # Stores the resultant count of pairs count = 0 for i in range(0, 2**N): # Iterate over the range if i ^ (i + 1) == (i + 2) ^ (i + 3): count += 1 return count# Driver Codeif __name__ == '__main__': N = 3 # Function call print(countOfvalues(N)) |
C#
// C# Program of the above approachusing System;class GFG{ // Function to find number of integers // satisfying the condition public static int countOfvalues(int N) { // Stores the resultant count of pairs int count = 0; for (int i = 0; i < (1 << N); i++) { // Iterate over the range if ((i ^ (i + 1)) == ((i + 2) ^ (i + 3))) count += 1; } return count; } // Driver Code public static void Main () { int N = 3; // Function call Console.Write(countOfvalues(N)); }}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript code for the above approach // Function to find number of integers // satisfying the condition function countOfvalues(N) { // Stores the resultant count of pairs let count = 0; for (let i = 0; i < (1 << N); i++) { // Iterate over the range if ((i ^ (i + 1)) == ((i + 2) ^ (i + 3))) count += 1; } return count; } // Driver Code let N = 3; // Function call document.write(countOfvalues(N)); // This code is contributed by Potta Lokesh </script> |
4
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The problem can be solved efficiently based on the following mathematical idea:
- If x is such that it is a even number then x+2 is also a even number and both (x+1) and (x+3) will be odd numbers.
- Now two consecutive even and odd number has only a single bit difference only on their LSB position.
- So the bitwise XOR of (x and x+1) and (x+2 and x+3) both will be 1, when x is even.
- Therefore all the even numbers in the given range [0, 2N−1] is a possible value of x.
So total number of such values are (2N – 1)/2 = 2N-1
Follow the illustration below to visualize the idea better:
Illustration:
Consider N = 3. So the numbers are in range [0, 7]
All even numbers in the range are 0, 2, 4 and 6
=> When x = 0: 0 ⊕ 1 = 1 and 2 ⊕ 3 = 1. Therefore the relation holds
=> When x = 2: 2 ⊕ 3 = 1 and 4 ⊕ 5 = 1. Therefore the relation holds
=> When x = 4. 4 ⊕ 5 = 1 and 6 ⊕ 7 = 1. Therefore the relation holds
=> When x = 6: 6 ⊕ 7 = 1 and 8 ⊕ 9 = 1. Therefore the relation holds.Now for the odd numbers if it is done:
=> When x = 1: 1 ⊕ 2 = 3 and 3 ⊕ 4 = 7. Therefore the relation does not hold.
=> When x = 3: 3 ⊕ 4 = 7 and 5 ⊕ 6 = 3. Therefore the relation does not hold.
=> When x = 5: 5 ⊕ 6 = 3 and 7 ⊕ 8 = 15. Therefore the relation does not hold.
=> When x = 7: 7 ⊕ 8 = 15 and 9 ⊕ 10 = 3. Therefore the relation does not hold.So total possible values are 4 = 23-1
Therefore to get the answer calculate the value of 2N-1 for given N
Below is the implementation of the above approach.
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate// the number of possible valuesint countValues(int N) { return pow(2, N - 1); }// Driver Codeint main(){ int N = 3; // Function call cout << countValues(N); return 0;}// This code is contributed by Rohit Pradhan |
Java
// Java code to implement the above approachclass GFG { // Function to calculate // the number of possible values public static int countValues(int N) { return (int)Math.pow(2, N - 1); } public static void main(String[] args) { int N = 3; // Function call System.out.println(countValues(N)); }}//This code is contributed by phasing17 |
Python3
# Python code to implement the above approach# Function to calculate # the number of possible valuesdef countOfValues (N): return pow(2, N - 1)# Driver codeif __name__ == '__main__': N = 3 # Function call res = countOfValues(N) print(res) |
C#
// C# program for above approachusing System;using System.Collections.Generic;public class GFG{ // Function to calculate // the number of possible values public static int countValues(int N) { return (int)Math.Pow(2, N - 1); } // Driver code public static void Main(String[] args) { int N = 3; // Function call Console.Write(countValues(N)); }}// This code is contributed by code_hunt. |
Javascript
<script>// JavaScript code to implement the above approach// Function to calculate// the number of possible valuesfunction countValues(N) { return Math.pow(2, N - 1); }// Driver Codelet N = 3;// Function calldocument.write(countValues(N));// This code is contributed by shinjanpatra</script> |
4
Time Complexity: O(log(N))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
