Find all subarray index ranges in given Array with set bit sum equal to X

0 0 12 minutes read

Given an array arr (1-based indexing) of length N and an integer X, the task is to find and print all index ranges having a set bit sum equal to X in the array.

Examples:

Input: A[] = {1 4 3 5 7}, X = 4
Output: (1, 3), (3, 4)
Explanation: In the above array subarray having set bit sum equal to X (= 4).
Starting from index 1 to 3. {1 4 3} = (001) + (100) + (011) = 4 and
other one is from 3 to 4 {3, 5} = (011) + (101) = 4.

Input: arr[] = {5, 3, 0, 4, 10}, X = 7
Output: (1 5)
Explanation: In the above array subarrays having set bit sum equal to X(= 7) start from 1 to 5 only.

Approach: The problem is solved using two pointer approach.

Write a function countSetBit to count the number of set bits.
- Initialize a counter c=0, to store the individual count for every number in the array.
- Iterate over the array and check for every set bit and increase the counter.
- replace every number with the count of a number of set bits
Write a function to print a range of subarrays PrintIndex
Run a loop using two pointers i and j and check for the sum as follow:
- If the current index sum is less than X then, add the value at arr[j] in currsum
- else if the sum is equal to X push back the start and end index of the array and increment the counter i.
- else decrement the counter, subtract the value at arr[i] from currsum.
- Repeat the same for all elements.

Below is the implementation of the above method :

C++

// C++ program to Find all range
// Having set bit sum X  in array
#include <bits/stdc++.h>
using namespace std;
 
// Function to replace elements
// With their set bit count
void countSetBit(vector<int>& arr, int n)
{
    int c = 0, i;
 
    for (i = 0; i < n; i++) {
 
        int x = arr[i];
        while (x) {
            int l = x % 10;
            if (x & 1)
                c++;
            x /= 2;
        }
        // Replace array element
        // to set bit count
        arr[i] = c;
        c = 0;
    }
}
 
// Function to find range of subarrays
// having set bit sum equal to X.
void PrintIndex(vector<int> arr, int N, int X,
                vector<int>& v)
{
 
    int i = 0, j = 0, currSum = arr[0];
    while (j < N && i < N) {
        if (currSum == X) {
            // push back index i start
            // point ans end point j
            // when sum == X
 
            v.push_back(i + 1);
            v.push_back(j + 1);
 
            j++;
            currSum += arr[j];
        }
        // when current sum is
        // less than X increment j
        // and add arr[j]
        else if (currSum < X) {
            j++;
            currSum += arr[j];
        }
        // when current sum is
        // greater than X increment j
        // and subtract arr[i]
        else {
            currSum -= arr[i];
            i++;
        }
    }
}
 
// Driver code
int main()
{
    vector<int> v = { 1, 4, 3, 5, 7 };
    int X = 4;
    int N = v.size();
 
    // replace all the array element into
    // their set bit count value
    countSetBit(v, N);
 
    vector<int> ans;
 
    PrintIndex(v, N, X, ans);
 
    for (int i = 0; i < ans.size() - 1; i += 2)
        cout << "(" << ans[i] << " "
             << ans[i + 1] << ")"
             << " ";
 
    return 0;
}

Java

// JAVA code to implement the above approach
import java.util.*;
class GFG {
 
  // Function to replace elements
  // With their set bit count
  static void countSetBit(int[] arr, int n)
  {
    int c = 0, i;
 
    for (i = 0; i < n; i++) {
 
      int x = arr[i];
      while (x > 0) {
        int l = x % 10;
        if ((x & 1) == 1)
          c++;
        x /= 2;
      }
      // Replace array element
      // to set bit count
      arr[i] = c;
      c = 0;
    }
  }
 
  // Function to find range of subarrays
  // having set bit sum equal to X.
  static void PrintIndex(int[] arr, int N, int X,
                         ArrayList<Integer> v)
  {
 
    int i = 0, j = 0, currSum = arr[0];
    while (j < N && i < N) {
      if (currSum == X) {
        // push back index i start
        // point ans end point j
        // when sum == X
 
        v.add(i + 1);
        v.add(j + 1);
 
        j++;
        if (j < N)
          currSum += arr[j];
      }
      // when current sum is
      // less than X increment j
      // and add arr[j]
      else if (currSum < X) {
        j++;
        if (j < N)
          currSum += arr[j];
      }
      // when current sum is
      // greater than X increment j
      // and subtract arr[i]
      else {
        currSum -= arr[i];
        i++;
      }
    }
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int[] v = { 1, 4, 3, 5, 7 };
    int X = 4;
    int N = v.length;
 
    // replace all the array element into
    // their set bit count value
    countSetBit(v, N);
 
    ArrayList<Integer> ans = new  ArrayList<Integer>();
 
    PrintIndex(v, N, X, ans);
 
    for (int i = 0; i < ans.size() - 1; i += 2)
      System.out.print("(" + ans.get(i) + " " + ans.get(i + 1)
                       + ")"
                       + " ");
  }
}
 
// This code is contributed by sanjoy_62.

Python3

# Python program to Find all range
# Having set bit sum X in array
 
# Function to replace elements
# With their set bit count
def countSetBit(arr, n):
    c = 0
 
    for i in range(n):
        x = arr[i]
        while (x):
            l = x % 10
            if (x & 1):
                c += 1
            x = x // 2
                 
        # Replace array element
        # to set bit count
        arr[i] = c
        c = 0
 
# Function to find range of subarrays
# having set bit sum equal to X.
def PrintIndex(arr, N, X, v):
 
    i,j,currSum = 0,0,arr[0]
 
    while (j < N and i < N): 
 
        if (currSum == X): 
                 
            # append back index i start
            # point ans end point j
            # when sum == X
 
            v.append(i + 1)
            v.append(j + 1)
 
            j += 1
            if(j<N):
                currSum += arr[j]
                 
        # when current sum is
        # less than X increment j
        # and add arr[j]
        elif (currSum < X):
            j += 1
            if(j<N):
                currSum += arr[j]
                 
        # when current sum is
        # greater than X increment j
        # and subtract arr[i]
        else:
            currSum -= arr[i]
            i += 1
 
# Driver code
v = [1, 4, 3, 5, 7]
X = 4
N = len(v)
 
# replace all the array element into
# their set bit count value
countSetBit(v, N)
ans = []
PrintIndex(v, N, X, ans)
 
for i in range(0,len(ans) - 1,2):
    print(f"({ans[i]} {ans[i + 1]})",end=" ")
 
# This code is contributed by shinjanpatra

C#

// C# program to Find all range
// Having set bit sum X  in array
using System;
using System.Collections;
 
class GFG {
 
  // Function to replace elements
  // With their set bit count
  static void countSetBit(int[] arr, int n)
  {
    int c = 0, i;
 
    for (i = 0; i < n; i++) {
 
      int x = arr[i];
      while (x > 0) {
        int l = x % 10;
        if ((x & 1) == 1)
          c++;
        x /= 2;
      }
      // Replace array element
      // to set bit count
      arr[i] = c;
      c = 0;
    }
  }
 
  // Function to find range of subarrays
  // having set bit sum equal to X.
  static void PrintIndex(int[] arr, int N, int X,
                         ArrayList v)
  {
 
    int i = 0, j = 0, currSum = arr[0];
    while (j < N && i < N) {
      if (currSum == X) {
        // push back index i start
        // point ans end point j
        // when sum == X
 
        v.Add(i + 1);
        v.Add(j + 1);
 
        j++;
        if (j < N)
          currSum += arr[j];
      }
      // when current sum is
      // less than X increment j
      // and add arr[j]
      else if (currSum < X) {
        j++;
        if (j < N)
          currSum += arr[j];
      }
      // when current sum is
      // greater than X increment j
      // and subtract arr[i]
      else {
        currSum -= arr[i];
        i++;
      }
    }
  }
 
  // Driver code
  public static void Main()
  {
    int[] v = { 1, 4, 3, 5, 7 };
    int X = 4;
    int N = v.Length;
 
    // replace all the array element into
    // their set bit count value
    countSetBit(v, N);
 
    ArrayList ans = new ArrayList();
 
    PrintIndex(v, N, X, ans);
 
    for (int i = 0; i < ans.Count - 1; i += 2)
      Console.Write("(" + ans[i] + " " + ans[i + 1]
                    + ")"
                    + " ");
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
    // JavaScript program to Find all range
    // Having set bit sum X in array
 
    // Function to replace elements
    // With their set bit count
    const countSetBit = (arr, n) => {
        let c = 0, i;
 
        for (i = 0; i < n; i++) {
 
            let x = arr[i];
            while (x) {
                let l = x % 10;
                if (x & 1)
                    c++;
                x = parseInt(x / 2);
            }
             
            // Replace array element
            // to set bit count
            arr[i] = c;
            c = 0;
        }
    }
 
    // Function to find range of subarrays
    // having set bit sum equal to X.
    const PrintIndex = (arr, N, X, v) => {
 
        let i = 0, j = 0, currSum = arr[0];
        while (j < N && i < N) 
        {
            if (currSum == X) 
            {
             
                // push back index i start
                // point ans end point j
                // when sum == X
 
                v.push(i + 1);
                v.push(j + 1);
 
                j++;
                currSum += arr[j];
            }
             
            // when current sum is
            // less than X increment j
            // and add arr[j]
            else if (currSum < X) {
                j++;
                currSum += arr[j];
            }
             
            // when current sum is
            // greater than X increment j
            // and subtract arr[i]
            else {
                currSum -= arr[i];
                i++;
            }
        }
    }
 
    // Driver code
    let v = [1, 4, 3, 5, 7];
    let X = 4;
    let N = v.length;
 
    // replace all the array element into
    // their set bit count value
    countSetBit(v, N);
 
    let ans = [];
 
    PrintIndex(v, N, X, ans);
 
    for (let i = 0; i < ans.length - 1; i += 2)
        document.write(`(${ans[i]} ${ans[i + 1]}) `);
 
// This code is contributed by rakeshsahni
 
</script>

Output

(1 3) (3 4)

Time Complexity: O(N * d) where d is the count of bits in an array element
Auxiliary Space: O(N)

Another Approach:

The code defines a function called countSetBit that takes an integer x and returns the number of set bits in its binary representation.
The code also defines another function called printSubarraysWithSetBitSumX that takes a vector of integers arr and an integer X. This function prints all the subarrays of arr whose sum of set bits is equal to X.
Inside the printSubarraysWithSetBitSumX function, the code initializes some variables: n is the size of the input vector arr, i and j are two pointers initially set to 0, and currSum is the current sum of set bits.
The code enters a while loop with a condition of j < n. This loop iterates through all the elements of the input vector arr.
Inside the while loop, the code adds the count of set bits of the current element to the currSum variable and increments j by 1.
The code then enters another while loop with a condition of currSum > X. This loop removes the set bit count of the element pointed by i from the currSum variable and increments i by 1 until the currSum becomes less than or equal to X.
If the currSum is equal to X after the above while loop, the code prints the indices of the subarray whose sum of set bits is equal to X.
The while loop in step 4 continues until j reaches the end of the input vector arr.
Finally, the main function creates a vector arr containing integers {1, 4, 3, 5, 7} and sets X to 4. It then calls the printSubarraysWithSetBitSumX function with these arguments, which prints “(1, 3) (3, 4)” to the console.

Below is the implementation of the above approach:

C++

#include <iostream>
#include <vector>
using namespace std;
 
int countSetBit(int x) {
    int count = 0;
    while (x > 0) {
        count += x & 1;
        x >>= 1;
    }
    return count;
}
 
void printSubarraysWithSetBitSumX(vector<int>& arr, int X) {
    int n = arr.size();
    int i = 0, j = 0, currSum = 0;
    while (j < n) {
        currSum += countSetBit(arr[j]);
        j++;
        while (currSum > X) {
            currSum -= countSetBit(arr[i]);
            i++;
        }
        if (currSum == X) {
            cout << "(" << i + 1 << ", " << j << ") ";
        }
    }
}
 
int main() {
    vector<int> arr = {1, 4, 3, 5, 7};
    int X = 4;
    printSubarraysWithSetBitSumX(arr, X); // prints (1, 3) (3, 4)
    return 0;
}

Java

import java.util.*;
 
public class SubarraysWithSetBitSum {
    public static int countSetBit(int x) {
        int count = 0;
        while (x > 0) {
            count += x & 1;
            x >>= 1;
        }
        return count;
    }
 
    public static void printSubarraysWithSetBitSumX(ArrayList<Integer> arr, int X) {
        int n = arr.size();
        int i = 0, j = 0, currSum = 0;
        while (j < n) {
            currSum += countSetBit(arr.get(j));
            j++;
            while (currSum > X) {
                currSum -= countSetBit(arr.get(i));
                i++;
            }
            if (currSum == X) {
                System.out.print("(" + (i + 1) + ", " + j + ") ");
            }
        }
    }
 
    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<Integer>(Arrays.asList(1, 4, 3, 5, 7));
        int X = 4;
        printSubarraysWithSetBitSumX(arr, X); // prints (1, 3) (3, 4)
    }
}

Python3

def count_set_bits(x):
    # Function to count the number of set bits (1s) in a binary representation of 'x'
    count = 0
    while x > 0:
        count += x & 1  # Add the least significant bit of 'x' to the count
        x >>= 1  # Right shift 'x' to check the next bit
    return count
 
def print_subarrays_with_set_bit_sum_x(arr, X):
    n = len(arr)  # Get the length of the input array 'arr'
    i, j, curr_sum = 0, 0, 0  # Initialize variables for subarray tracking
 
    while j < n:  # Iterate through the array using a sliding window (j moves forward)
        curr_sum += count_set_bits(arr[j])  # Add the count of set bits in 'arr[j]' to 'curr_sum'
        j += 1
 
        while curr_sum > X:  # If 'curr_sum' exceeds the target 'X', move the window's left end (i) forward
            curr_sum -= count_set_bits(arr[i])  # Subtract the count of set bits in 'arr[i]' from 'curr_sum'
            i += 1
 
        if curr_sum == X:  # If 'curr_sum' matches the target 'X', print the subarray
            print(f"({i + 1}, {j}) ", end='')
 
# Main function
if __name__ == "__main__":
    arr = [1, 4, 3, 5, 7]  # Input array
    X = 4  # Target sum of set bits
    print_subarrays_with_set_bit_sum_x(arr, X)  # Call the function to find and print subarrays with the target sum

C#

using System;
using System.Collections.Generic;
 
public class SubarraysWithSetBitSum {
    // Function to count the number of set bits in a number
    public static int CountSetBit(int x) {
        int count = 0;
        while (x > 0) {
            count += x & 1; // Increment count if the last bit is 1
            x >>= 1; // Right shift the number to check the next bit
        }
        return count;
    }
 
    // Function to find and print subarrays with a given set bit sum
    public static void PrintSubarraysWithSetBitSumX(List<int> arr, int X) {
        int n = arr.Count;
        int i = 0, j = 0, currSum = 0;
        while (j < n) {
            currSum += CountSetBit(arr[j]); // Calculate set bit sum for the current element
            j++;
             
            // Slide the window to the right while current set bit sum is greater than X
            while (currSum > X) {
                currSum -= CountSetBit(arr[i]); // Remove set bit count of the left element
                i++;
            }
             
            // If the current set bit sum matches X, print the subarray indices
            if (currSum == X) {
                Console.Write("(" + (i + 1) + ", " + j + ") ");
            }
        }
    }
 
    public static void Main(string[] args) {
        List<int> arr = new List<int> { 1, 4, 3, 5, 7 };
        int X = 4;
        PrintSubarraysWithSetBitSumX(arr, X); // prints (1, 3) (3, 4)
    }
}

Javascript

function countSetBit(x) {
    let count = 0;
    while (x > 0) {
        count += x & 1;
        x >>= 1;
    }
    return count;
}
 
function printSubarraysWithSetBitSumX(arr, X) {
    const n = arr.length;
    let i = 0, j = 0, currSum = 0;
    while (j < n) {
        currSum += countSetBit(arr[j]);
        j++;
        while (currSum > X) {
            currSum -= countSetBit(arr[i]);
            i++;
        }
        if (currSum === X) {
            console.log(`(${i + 1}, ${j})`);
        }
    }
}
 
const arr = [1, 4, 3, 5, 7];
const X = 4;
printSubarraysWithSetBitSumX(arr, X); // prints (1, 3) (3, 4)

Output

(1, 3) (3, 4)

Time complexity: O(n*logx)
Auxiliary Space: O(n)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!