Given a number N. The task is to count the number of distinct XOR of any possible pairs using numbers from 1 to N inclusive.
Examples:
Input: N = 3
Output: 4
Explanation: Following are the all possible pairs using elements from 1 to N inclusive.
1^1 = 0
1^2 = 3
1^3 = 2
2^2 = 0
2^3 = 1
3^3 = 0
Therefore, there are 4 distinct possible XOR values.Input: N = 2
Output: 2
Naive Approach:
The naive approach to solve this problem is to generate all possible pairs from 1 to N and then calculate their XOR and store it in a set. After calculating XOR of all pairs, the size of the set will be the count of distinct XOR of any possible pairs.
Algorithm:
- Initialize a variable count to 0.
- Loop from i = 1 to N, and within this loop, loop from j = i to N.
- For each pair (i, j), calculate the XOR value using i^j.
- If this XOR value is not already present in the set of distinct XOR values, add it to the set and increment the count variable by 1.
- After both loops, return the count variable as the answer.
Below is the implementation of the approach:
C++
// C++ code for the approach#include <bits/stdc++.h>using namespace std;// Function to coint distinct Xorint countDistinctXOR(int n) { // to store distinct XOR values set<int> distinctXOR; for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { // calculating XOR of pair (i, j) int XOR = i ^ j; // inserting XOR in set distinctXOR.insert(XOR); } } // returning size of the set return distinctXOR.size(); }// Driver's Codeint main() { int n = 3; cout << countDistinctXOR(n) << endl; return 0;} |
Java
import java.util.HashSet;public class Main { // Function to count distinct XOR values static int countDistinctXOR(int n) { // To store distinct XOR values HashSet<Integer> distinctXOR = new HashSet<>(); for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { // Calculating XOR of pair (i, j) int XOR = i ^ j; // Inserting XOR in the HashSet distinctXOR.add(XOR); } } // Returning the size of the HashSet return distinctXOR.size(); } // Driver's Code public static void main(String[] args) { int n = 3; System.out.println(countDistinctXOR(n)); }} |
Python3
# Python3 code for the approach# Function to coint distinct Xordef countDistinctXOR(n): # to store distinct XOR values distinctXOR = set() for i in range(1, n+1): for j in range(i, n+1): # calculating XOR of pair (i, j) XOR = i ^ j # inserting XOR in set distinctXOR.add(XOR) return len(distinctXOR) # Driver's Coden = 3print(countDistinctXOR(n)) |
C#
using System;using System.Collections.Generic;public class GFG { // Function to count distinct XOR public static int CountDistinctXOR(int n) { // To store distinct XOR values HashSet<int> distinctXOR = new HashSet<int>(); for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { // Calculating XOR of pair (i, j) int XOR = i ^ j; // Inserting XOR in HashSet distinctXOR.Add(XOR); } } // Returning the size of the HashSet return distinctXOR.Count; } // Driver's Code public static void Main(string[] args) { int n = 3; Console.WriteLine(CountDistinctXOR(n)); }} |
Javascript
// Javascript code for the approach// Function to coint distinct Xorfunction countDistinctXOR(n) { // to store distinct XOR values let distinctXOR = new Set(); for (let i = 1; i <= n; i++) { for (let j = i; j <= n; j++) { // calculating XOR of pair (i, j) let XOR = i ^ j; // inserting XOR in set distinctXOR.add(XOR); } } return distinctXOR.size;}// Driver's Codelet n = 3;console.log(countDistinctXOR(n)); |
Output
4
Time complexity: O(N^2) because the outer loop runs N times and the inner loop runs N-i times for each i, so the total number of iterations is 1+2+…+N = N*(N+1)/2.
Auxiliary Space: O(d) where d is number of distinct XOR possible. This is because set has been created to store values of XOR.
Approach: This problem is observation-based. Follow the steps below to solve the given problem.
- For N = 1 and N = 2 the require output are 1 and 2 respectively.
- Now for N≥3, there are two possible cases:
- If N is not a power of two then, there will be a total of ‘t’ numbers where t is the power of 2 which is just next to the number N. They vary from [0 to t – 1]. Because let’s say, N = 5 or 6 or 7 In all the above cases values varies from [0, 1, 2, 3, 4, 5, 6, 7].
- If N is a power of two then, all the numbers will be possible except the number itself. Because let’s say, N = 4 in binary it is “100” so as we know XOR operation gives “1″ if both bits are different else it gives 0. Possible values are [0, 1, 2, 3,
4, 5, 6, 7].
Below is the implementation of the above approach.
C++
// C++ code to implement above approach#include <cmath>#include <iostream>using namespace std;int findDistinctXOR(int n){ // Corner case if (n == 1) { cout << 1 << endl; } if (n == 2) { cout << 2 << endl; } long long x, next; x = log2(n); // if n is power of two if ((n & (n - 1)) == 0) { next = pow(2, x + 1); cout << next - 1 << endl; } else { next = pow(2, x + 1); cout << next << endl; }}// Driver Codeint main(){ int N = 3; findDistinctXOR(N); return 0;} |
Java
// Java code to implement above approach//include <cmath>import java.util.*;class GFG{static void findDistinctXOR(int n){ // Corner case if (n == 1) { System.out.print(1 +"\n"); } if (n == 2) { System.out.print(2 +"\n"); } long x, next; x = (long) Math.log(n); // if n is power of two if ((n & (n - 1)) == 0) { next = (long) Math.pow(2, x + 1); System.out.print(next - 1 +"\n"); } else { next = (long) Math.pow(2, x + 1); System.out.print(next +"\n"); }}// Driver Codepublic static void main(String[] args){ int N = 3; findDistinctXOR(N);}}// This code is contributed by 29AjayKumar |
Python3
# Python code for the above approachimport math as Mathdef findDistinctXOR(n): # Corner case if (n == 1): print(1) if (n == 2): print(2) x = None next = None x = Math.floor(Math.log2(n)) # if n is power of two if ((n & (n - 1)) == 0): next = Math.pow(2, x + 1) print((next - 1)) else: next = Math.pow(2, x + 1) print(int(next))# Driver CodeN = 3findDistinctXOR(N)# This code is contributed by Saurabh Jaiswal |
C#
// C# code to implement above approachusing System;class GFG{static void findDistinctXOR(int n){ // Corner case if (n == 1) { Console.WriteLine(1); } if (n == 2) { Console.WriteLine(2); } long x, next; x = (long)Math.Log(n, 2); // If n is power of two if ((n & (n - 1)) == 0) { next = (long)Math.Pow(2, x + 1); Console.WriteLine(next - 1); } else { next = (long)Math.Pow(2, x + 1); Console.WriteLine(next); }}// Driver Codepublic static void Main(){ int N = 3; findDistinctXOR(N);}}// This code is contributed by ukasp |
Javascript
<script> // JavaScript code for the above approach function findDistinctXOR(n) { // Corner case if (n == 1) { document.write(1 + "<br>") } if (n == 2) { document.write(2 + "<br>") } let x, next; x = Math.floor(Math.log2(n)); // if n is power of two if ((n & (n - 1)) == 0) { next = Math.pow(2, x + 1); document.write((next - 1) + "<br>") } else { next = Math.pow(2, x + 1); document.write(next + "<br>") } } // Driver Code let N = 3; findDistinctXOR(N); // This code is contributed by Potta Lokesh </script> |
Output
4
Time Complexity: O(log(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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
