Given a positive integer N, the task is to find the total count of set bits by performing Bitwise XOR on all possible adjacent elements in the range [0, N].
Examples:
Input: N = 4
Output: 7
Explanation:
Bitwise XOR of 0 and 1 = 001 and count of set bits = 1
Bitwise XOR of 1 and 2 = 011 and count of set bits = 2
Bitwise XOR of 2 and 3 = 001 and count of set bits = 1
Bitwise XOR of 3 and 4 = 111 and count of set bits = 3
Therefore, the total count of set bits by performing the XOR operation on all possible adjacent elements of the range [0, N] = (1 + 2 + 1 + 3) = 7Input: N = 7
Output: 11
Naive Approach: The simplest approach to solve this problem is to iterate over the range [0, N] and count all possible set bits by performing Bitwise XOR on each adjacent element over the range [0, N]. Finally, print the total count of all possible set bits.
Time Complexity: O(N * log2N)
Auxiliary Space: O(1)
Efficient approach: To optimize the above approach, the idea is based on the following observations:
If the position of the rightmost set bit of X is K, then the count of set bits in (X ^ (X – 1)) must be K.
Follow the steps below to solve the problem:
- Initialize a variable, say bit_position to store all possible values of the right most bit over the range [0, N].
- Initialize a variable, say total_set_bits to store the sum of all possible set bits by performing the Bitwise XOR operation on all possible adjacent elements over the range [0, N].
- Iterate over the range [0, N] and Update N = N – (N + 1) / 2 and total_set_bits += ((N + 1) / 2 * bit_position).
- Finally, print the value of total_set_bits.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to count of set bits in Bitwise// XOR of adjacent elements up to Nint countXORSetBitsAdjElemRange1_N(int N){ // Stores count of set bits by Bitwise // XOR on adjacent elements of [0, N] int total_set_bits = 0; // Stores all possible values on // right most set bit over [0, N] int bit_Position = 1; // Iterate over the range [0, N] while (N) { total_set_bits += ((N + 1) / 2 * bit_Position); // Update N N -= (N + 1) / 2; // Update bit_Position bit_Position++; } return total_set_bits;}// Driver Codeint main(){ int N = 4; cout << countXORSetBitsAdjElemRange1_N(N); return 0;} |
Java
// Java program to implement// the above approachimport java.io.*;import java.util.*; class GFG{ // Function to count of set bits in Bitwise// XOR of adjacent elements up to Nstatic int countXORSetBitsAdjElemRange1_N(int N){ // Stores count of set bits by Bitwise // XOR on adjacent elements of [0, N] int total_set_bits = 0; // Stores all possible values on // right most set bit over [0, N] int bit_Position = 1; // Iterate over the range [0, N] while (N != 0) { total_set_bits += ((N + 1) / 2 * bit_Position); // Update N N -= (N + 1) / 2; // Update bit_Position bit_Position++; } return total_set_bits;} // Driver Codepublic static void main(String[] args){ int N = 4; System.out.println(countXORSetBitsAdjElemRange1_N(N));}} // This code is contributed by susmitakundugoaldanga |
Python3
# Python3 program to implement# the above approach# Function to count of set bits in Bitwise# XOR of adjacent elements up to Ndef countXORSetBitsAdjElemRange1_N(N): # Stores count of set bits by Bitwise # XOR on adjacent elements of [0, N] total_set_bits = 0 # Stores all possible values on # right most set bit over [0, N] bit_Position = 1 # Iterate over the range [0, N] while (N): total_set_bits += ((N + 1) // 2 * bit_Position) # Update N N -= (N + 1) // 2 # Update bit_Position bit_Position += 1 return total_set_bits# Driver Codeif __name__ == '__main__': N = 4 print(countXORSetBitsAdjElemRange1_N(N))# This code is contributed by SURENDRA_GANGWAR |
C#
// C# program to implement// the above approach using System; class GFG{ // Function to count of set bits in Bitwise// XOR of adjacent elements up to Nstatic int countXORSetBitsAdjElemRange1_N(int N){ // Stores count of set bits by Bitwise // XOR on adjacent elements of [0, N] int total_set_bits = 0; // Stores all possible values on // right most set bit over [0, N] int bit_Position = 1; // Iterate over the range [0, N] while (N != 0) { total_set_bits += ((N + 1) / 2 * bit_Position); // Update N N -= (N + 1) / 2; // Update bit_Position bit_Position++; } return total_set_bits;} // Driver Codepublic static void Main(){ int N = 4; Console.Write(countXORSetBitsAdjElemRange1_N(N));}}// This code is contributed by code_hunt |
Javascript
<script>// Javascript program to implement// the above approach// Function to count of set bits in Bitwise// XOR of adjacent elements up to Nfunction countXORSetBitsAdjElemRange1_N(N){ // Stores count of set bits by Bitwise // XOR on adjacent elements of [0, N] let total_set_bits = 0; // Stores all possible values on // right most set bit over [0, N] let bit_Position = 1; // Iterate over the range [0, N] while (N) { total_set_bits += (Math.floor((N + 1) / 2) * bit_Position); // Update N N -= Math.floor((N + 1) / 2); // Update bit_Position bit_Position++; } return total_set_bits;}// Driver Codelet N = 4;document.write(countXORSetBitsAdjElemRange1_N(N));// This code is contributed by _saurabh_jaiswal</script> |
7
Time complexity:O(Log2N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
