Given a positive integer N, the task is to find the number of ways to represent N as Bitwise XOR of distinct positive integers less than or equal to N.
Examples:
Input: N = 5
Output: 4
Explanation: The given number N(= 5) can be represented as:
- 5 = 5
- 5 = (4 ^ 1)
- 5 = (5 ^ 3 ^ 2 ^ 1)
- 5 = (4 ^ 3 ^ 2)
Therefore, the total count is 4.
Input: N = 6
Output: 8
Naive Approach: The simplest approach to solve the problem is to find all subsets of first N natural numbers and count those subsets having Bitwise XOR value N. After checking for all the subsets, print the total value of the count obtained.
Time Complexity: O(N * 2N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by using the observation that the number of ways to represent N as the Bitwise XOR of distinct positive integers is given by 
.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// Function to count number of ways// to represent N as the Bitwise// XOR of distinct integersvoid countXorPartition(int N){ // Count number of subsets using // above-mentioned formula double a = pow(2, floor(N - log(N + 1) / log(2))); // Print the resultant count cout << a;} // Driver Codeint main(){ int N = 5; countXorPartition(N);}// This code is contributed by SURENDRA_GANGWAR |
Java
// java program for the above approachimport java.io.*;class GFG{// Function to count number of ways// to represent N as the Bitwise// XOR of distinct integersstatic void countXorPartition(int N){ // Count number of subsets using // above-mentioned formula double a = Math.pow(2, (int)(N - Math.log(N + 1) / Math.log(2))); // Print the resultant count System.out.print(a);} // Driver Codepublic static void main(String[] args){ int N = 5; countXorPartition(N);}}// This code is contributed by shivanisinghss2110 |
Python
# Python program for the above approachfrom math import * # Function to count number of ways# to represent N as the Bitwise# XOR of distinct integersdef countXorPartition(N): # Count number of subsets using # above-mentioned formula a = 2**floor(N - log(N + 1)/log(2)) # Print the resultant count print(int(a))# Driver CodeN = 5countXorPartition(N) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to count number of ways// to represent N as the Bitwise// XOR of distinct integersstatic void countXorPartition(int N){ // Count number of subsets using // above-mentioned formula double a = Math.Pow(2, (int)(N - Math.Log(N + 1) / Math.Log(2))); // Print the resultant count Console.Write(a);} // Driver Codepublic static void Main(){ int N = 5; countXorPartition(N);}}// This code is contributed by ipg2016107. |
Javascript
<script>// JavaScript program for the above approach// Function to count number of ways// to represent N as the Bitwise// XOR of distinct integersfunction countXorPartition(N){ // Count number of subsets using // above-mentioned formula let a = Math.pow(2, Math.floor(N - Math.log(N + 1) / Math.log(2))); // Print the resultant count document.write(a);} // Driver Code let N = 5; countXorPartition(N);</script> |
4
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
