Queries For Sum Of Bitwise And Of All Subarrays In A Range In C++

Introduction:

In this tutorial, the objective is to calculate the total sum of bitwise AND operation outcomes for all potential subarrays within a specified index range in an array. Bitwise AND is a process that involves comparing each pair of corresponding bits in two binary numbers and generating a new binary number based on the logical AND operation.

Program:

#include <iostream>
#include <vector>
using namespace std;
// Function to calculate the sum of bitwise AND all subarrays in a range
int sumBitwiseAndInRange(int arr[], int n, int left, int right) {
    int result = 0;
    // Iterate through each bit position (32 bits for integers)
    for (int bit = 0; bit < 32; ++bit) {
        int countOnes = 0;  // Count of set bits at the current bit position
        // Iterate through each element in the given range
        for (int i = left; i <= right; ++i) {
            // Check if the bit at the current position is set (1)
            if ((arr[i] & (1 << bit)) != 0) {
                countOnes++;
            }
        }
        // If the count of set bits is equal to the number of elements in the range,
        // it means that the AND of the bit at the current position will be 1 in all subarrays.
        // So, set the corresponding bit in the result.
        if (countOnes == (right - left + 1)) {
            result |= (1 << bit);
        }
    }
    return result;
}
int main() {
    // Example usage
    int arr[] = {5, 2, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    int left = 0, right = 2;
    // Calculate the sum of bitwise AND of all subarrays in the given range
    int result = sumBitwiseAndInRange(arr, n, left, right);
    cout << "Sum of bitwise AND of all subarrays in the range [" << left << ", " << right << "] is: " << result << endl;
    return 0;
}

Output:

Sum of bitwise AND of all subarrays in the range [0, 2] is: 0

Explanation:

• ✅ Main Goal:

The primary objective of this code is to calculate the total sum of bitwise AND operations for all potential subarrays within a specified range in an array.

• ✅ The function sumBitwiseAndInRange:

This function accepts three arguments: an array (arr), the array's size (n), and a specified range indicated by indices (left and right).

It employs a loop to iterate over each individual bit position from 0 to 31, as integers are commonly depicted using a 32-bit binary representation.

• ✅ Performing Bitwise AND Operation:

During each iteration, the loop calculates the total occurrences of a set bit (1) at the present index across the array elements falling within the defined range from left to right.

• ✅ Bit Setting Verification:

If the number of set bits at the current index matches the count of elements within the specified range, it indicates that the result of the AND operation will always be 1 for every subarray in that range. As a result, the bit at that position is set in the final outcome.

• ✅ Accumulating the Result:

The end outcome is achieved by merging the bitwise OR operation of all individual bits.

• ✅ Primary Function:

The primary function showcases how the sumBitwiseAndInRange function is applied using an example array ({5, 2, 8}) within a defined range (left = 0, right = 2).

It displays the total result of performing a bitwise AND operation on all subarrays within the given range.

Complexity analysis:

Time Complexity:

• ✅ The time complexity of the code mainly depends on two loops:
• ✅ The outer loop runs for each bit position (32 times for a 32-bit integer).
• ✅ The inner loop runs for each element in the specified range (left to right).
• ✅ Therefore, the overall time complexity can be expressed as O(32 * (right - left + 1)), which simplifies to O(right - left).

Space Complexity:

The code's space complexity is minimal and remains consistent. It involves a small number of integer variables (result, bit, countOnes, i), and the memory these variables use is not influenced by the input's magnitude. Therefore, we can categorize the space complexity as O(1) or constant.

Approach 1: Using observing patterns

The concept of this method involves examining the bitwise AND operation across a series of sequential numbers and recognizing that the outcome represents the shared initial segment of their binary notation. Subsequently, identifying and converting this shared segment back into decimal form allows us to obtain the ultimate outcome.

Program:

#include <iostream>
using namespace std;
int findCommonPrefix(int x, int y) {
    int shift = 0;
   // Keep shifting until the bits at the current position are different
    while (x < y) {
        x >>= 1;
        y >>= 1;
        shift++;
    }
    // Shift the common prefix back to the original position
    return x << shift;
}
int sumBitwiseAndInRange(int left, int right) {
    // Find the common prefix of the binary representation
    int commonPrefix = findCommonPrefix(left, right);
    return commonPrefix;
}
int main() {
    // Example usage
    int left = 5, right = 8;
    // Calculate the sum of bitwise AND for the specified range
    int result = sumBitwiseAndInRange(left, right);
    cout << "Sum of bitwise AND of all subarrays in the range [" << left << ", " << right << "] is: " << result << endl;
    return 0;
}

Output:

Sum of bitwise AND of all subarrays in the range [5, 8] is: 0

Explanation:

The findCommonPrefix method accepts two integer values (x and y) and identifies the common prefix of their binary forms. This is achieved by iteratively shifting both numbers to the right until the bits at the current position are not equal. Subsequently, the common prefix is shifted back to its initial position.

The sumBitwiseAndInRange function invokes the findCommonPrefix method to obtain the shared prefix of the binary format of the specified range from left to right.

The primary function showcases how to utilize the sumBitwiseAndInRange function with a sample range (left = 5, right = 8), computing and displaying the bitwise AND sum within the given range.

Complexity analysis:

Time Complexity:

• ✅ The time complexity of the findCommonPrefix function is determined by the number of bits in the binary representation of the smaller of the two numbers (x and y). The loop inside findCommonPrefix iterates until the bits at the current position are different, and in the worst case, it takes O(log(min(x, y))) steps.
• ✅ The sumBitwiseAndInRange function calls findCommonPrefix , so its time complexity is also O(log(min(left, right))).
• ✅ The main function and the rest of the code run in constant time because they involve basic operations.
• ✅ The overall time complexity is O(log(min(left, right))).

Space Complexity:

The space usage is minimal and remains constant. The algorithm utilizes a small number of integer variables (such as shift, commonPrefix, left, right, and result), and the memory required by these variables is unaffected by the size of the input.

In summary, the space complexity is O(1) or of constant order.

Approach 2: Using Bit Manipulation

The concept of this method involves conducting a bitwise AND operation across all elements within the designated range while monitoring the outcome for each individual bit position.

Program:

#include <iostream>
#include <climits>
using namespace std;
int sumBitwiseAndInRange(int left, int right) {
    // Initialize the result as INT_MAX (all bits set to 1)
    int result = INT_MAX;
    // Iterate through each bit position
    for (int bitPos = 31; bitPos >= 0; --bitPos) {
        // Check if the bit at the current position is set (1) in both left and right
        if ((left & (1 << bitPos)) && (right & (1 << bitPos))) {
            // If set, set the corresponding bit in the result
            result |= (1 << bitPos);
        } else {
            // If not set in both left and right, clear the corresponding bit in the result
            result &= ~(1 << bitPos);
        }
    }
    return result;
}
int main() {
    // Example usage
    int left = 5, right = 8;
    // Calculate the sum of bitwise AND for the specified range
    int result = sumBitwiseAndInRange(left, right);
    cout << "Sum of bitwise AND of all subarrays in the range [" << left << ", " << right << "] is: " << result << endl;
    return 0;
}

Output:

Sum of bitwise AND of all subarrays in the range [5, 8] is: 0

Explanation:

• ✅ The sumBitwiseAndInRange function takes two integers (left and right) representing the range.
• ✅ It initializes the result variable to INT_MAX to represent all bits set to 1.
• ✅ It iterates through each bit position (from the most significant bit to the least significant bit).
• ✅ For each bit position, it checks if the bit is set (1) in both left and right.
• ✅ If the bit is set in both, it sets the corresponding bit in the result.
• ✅ If the bit is not set in both, it clears the corresponding bit in the result.
• ✅ The final result is the sum of bitwise AND for the specified range.
• ✅ The main function demonstrates the usage of sumBitwiseAndInRange with an example range (left = 5, right = 8). It calculates and prints the sum of bitwise AND for the specified range.

Complexity analysis:

Time Complexity:

The time complexity of the sumBitwiseAndInRange method mainly depends on the iterative process that traverses each bit's position. This loop executes a fixed number of times (32 iterations in this scenario), resulting in a time complexity of O(1).

Space Complexity:

The code demonstrates a minimal and constant space complexity. It employs a handful of integer variables (result, left, right, bites), with their memory usage unaffected by the input size.

The time and space complexity of this code remains at O(1), which signifies a constant level of performance.

Approach 3: Using bitwise shift

It assists in determining the shared leftmost bits between the left and right values. These common leftmost bits are then used to set all subsequent bits to the right to 0.

Program:

#include <iostream>
using namespace std;
int sumBitwiseAndInRange(int left, int right) {
    int shift = 0;
    // Keep shifting until left and right become equal
    while (left < right) {
        left >>= 1;   // Right-shift 'left'
        right >>= 1;  // Right-shift 'right'
        shift++;      // Increment shift for each right-shift
    }
    // Left-shift either 'left' or 'right' by 'shift' to restore common leftmost bits
    return left << shift;
}
int main() {
    // Example usage
    int left = 5, right = 8;
    // Calculate the sum of bitwise AND for the specified range
    int result = sumBitwiseAndInRange(left, right);
    cout << "Sum of bitwise AND of all subarrays in the range [" << left << ", " << right << "] is: " << result << endl;
    return 0;
}

Output:

Sum of bitwise AND of all subarrays in the range [5, 8] is: 0

Explanation:

The function sumBitwiseAndInRange:

The function accepts a pair of integers, left and right, which indicate the specified range.

It sets a variable named shift to zero, which will be used to monitor the number of bits to be shifted.

The while loop persists until the values of left and right become equal.

In every loop cycle, both the left and right values undergo a rightward shift of 1 position, while the shift count is incremented.

After the iteration, it performs a left or right shift by a specified amount to realign the shared leftmost bits.

The end outcome is delivered.

In the

• ✅ Main Function:

The primary function showcases how to utilize sumBitwiseAndInRange with a specified range (left = 5, right = 8).

It computes and displays the total of bitwise AND operations within the given range.

Complexity analysis:

Time Complexity:

The primary factor influencing the time complexity of the sumBitwiseAndInRange function is predominantly the while loop. This loop continues iterating until the values of left and right are equal, a process that can consume logarithmic time under unfavorable conditions.

The time complexity is O(log(min(left, right))).

Space Complexity:

The algorithm maintains a consistently low and fixed space complexity. It operates with a minimal number of integer variables (specifically left, right, and shift), and the memory allocated for these variables remains unaffected by the size of the input.

The space complexity is O(1) or constant.

Approach 4: Using Common Prefix Bitmask

It identifies the shared leading bits between the left and right operands.

Set all bits to the right of the shared leftmost bits to 0.

Use a bitmask to retain the common leftmost bits.

Program:

#include <iostream>
#include <climits>
using namespace std;
int sumBitwiseAndInRange(int left, int right) {
    int commonBits = INT_MAX;
    // Continue until left and right have different common leftmost bits
    while ((left & commonBits) != (right & commonBits)) {
        commonBits &= (commonBits - 1);  // Set rightmost bit to 0
    }
    // Perform bitwise AND between left and commonBits to get the final result
    return left & commonBits;
}
int main() {
    // Example usage
    int left = 5, right = 8;
    // Calculate the sum of bitwise AND for the specified range
    int result = sumBitwiseAndInRange(left, right);
    cout << "Sum of bitwise AND of all subarrays in the range [" << left << ", " << right << "] is: " << result << endl;
    return 0;
}

Output:

Sum of bitwise AND of all subarrays in the range [5, 8] is: 0

Explanation:

Function sumBitwiseAndInRange:

• ✅ The function takes two integers, left and right, representing the range.
• ✅ It initializes a bitmask commonBits to INT_MAX, representing all bits set to 1.
• ✅ The while loop continues until left and right have different common leftmost bits (bits to the left of the rightmost differing bit).
• ✅ In each iteration, the rightmost bit of commonBits is set to 0 using (commonBits - 1).
• ✅ The final result is obtained by performing a bitwise AND between left and commonBits.

Main Objective:

• ✅ The primary purpose of this function is to showcase how the sumBitwiseAndInRange function operates within a specific range (left = 5, right = 8).
• ✅ It computes and displays the total bitwise AND sum for the defined range.

Complexity analysis:

Time Complexity:

• ✅ The efficiency of the sumBitwiseAndInRange method relies heavily on the while loop. This loop continues to execute until there are distinct common leftmost bits between the variables left and right. During each iteration, the rightmost bit of commonBits is modified to 0 through the operation (commonBits - 1). This process is completed in constant time.
• ✅ The total iterations within the while loop depend on the count of varying bits in the binary form of the numbers left and right. Hence, the time complexity is O(log(min(left, right))).

Space Complexity:

• ✅ The space complexity remains minimal and fixed. The algorithm utilizes a small number of integer variables (commonBits, left, right), and the memory they require is independent of the input size.
• ✅ The space complexity is denoted as O(1), indicating constant space usage.