Given an array arr[] consisting of positive integers and an array Q[][] consisting of queries, the task for every ith query is to count array elements from the range [Q[i][0], Q[i][1]] with only one set bit.
Examples:
Input: arr[] = {12, 11, 16, 8, 2, 5, 1, 3, 256, 1}, queries[][] = {{0, 9}, {4, 9}}
Output: 6 4
Explanation:
In the range of indices [0, 9], the elements arr[2] (= 16), arr[3](= 8), arr[4]( = 2), arr[6](= 1), arr[8](= 256), arr[9](= 1) have only 1 set bit.
In the range [4, 9], the elements arr[4] (= 2), arr[6](= 1), arr[8](= 256), arr[9] (= 1) have only 1 set bit.Input: arr[] = {2, 1, 101, 11, 4}, queries[][] = {{2, 4}, {1, 4}}
Output: 1 2
Naive Approach: The simplest approach for each query, is to iterate the range [l, r] and count the number of array elements having only one set bit by using Brian Kernighan’s Algorithm.
Time Complexity: O(Q * N*logN)
Auxiliary Space: O(1)
Efficient Approach: Follow the steps below to optimize the above approach:
- Initialize a prefix sum array to store the number of elements with only one set bit.
- The i-th index stores the count of array elements with only one set bit upto the ith index.
- For each query (i, j), return pre[j] – pre[i – 1], i.e. (inclusion-exclusion principle).
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check whether// only one bit is set or notint check(int x){ if (((x) & (x - 1)) == 0) return 1; return 0;}// Function to perform Range-queryint query(int l, int r, int pre[]){ if (l == 0) return pre[r]; else return pre[r] - pre[l - 1];}// Function to count array elements with a// single set bit for each range in a queryvoid countInRange(int arr[], int N, vector<pair<int, int> > queries, int Q){ // Initialize array for Prefix sum int pre[N] = { 0 }; pre[0] = check(arr[0]); for (int i = 1; i < N; i++) { pre[i] = pre[i - 1] + check(arr[i]); } int c = 0; while (Q--) { int l = queries.first; int r = queries.second; c++; cout << query(l, r, pre) << ' '; }}// Driver Codeint main(){ // Given array int arr[] = { 12, 11, 16, 8, 2, 5, 1, 3, 256, 1 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Given queries vector<pair<int, int> > queries = { { 0, 9 }, { 4, 9 } }; // Size of queries array int Q = queries.size(); countInRange(arr, N, queries, Q); return 0;} |
Java
// JAVA program for the above approach import java.util.*;import java.io.*;import java.math.*;public class GFG{ // Function to check whether // only one bit is set or not static int check(int x) { if (((x) & (x - 1)) == 0) return 1; return 0; } // Function to perform Range-query static int query(int l, int r, int[] pre) { if (l == 0) return pre[r]; else return pre[r] - pre[l - 1]; } // Function to count array elements with a // single set bit for each range in a query static void countInRange(int[] arr, int N, ArrayList<Pair> queries, int Q) { // Initialize array for Prefix sum int[] pre = new int[N]; pre[0] = check(arr[0]); for(int i = 1; i < N; i++) { pre[i] = pre[i - 1] + check(arr[i]); } int c = 0; int q = 0; while (q < Q) { int l = queries.get(q).item1; int r = queries.get(q).item2; c++; q++; System.out.print(query(l, r, pre) + " "); } } // A Pair class for handling queries in JAVA // As, there is no in-built function of Tuple static class Pair { int item1, item2; Pair(int item1, int item2) { this.item1 = item1; this.item2 = item2; } } // Driver code public static void main(String args[]) { // Given array int[] arr = { 12, 11, 16, 8, 2, 5, 1, 3, 256, 1 }; // Size of the array int N = arr.length; // Given queries ArrayList<Pair> queries = new ArrayList<Pair>(); queries.add(new Pair(4,9)); queries.add(new Pair(0,9)); // Size of queries array int Q = queries.size(); countInRange(arr, N, queries, Q); }}// This code is contributed by jyoti369 |
Python3
# Python 3 program for the above approach# Function to check whether# only one bit is set or notdef check(x): if (((x) & (x - 1)) == 0): return 1 return 0# Function to perform Range-querydef query(l, r, pre): if (l == 0): return pre[r] else: return pre[r] - pre[l - 1]# Function to count array elements with a# single set bit for each range in a querydef countInRange(arr, N, queries, Q): # Initialize array for Prefix sum pre = [0] * N pre[0] = check(arr[0]) for i in range(1, N): pre[i] = pre[i - 1] + check(arr[i]) c = 0 while (Q > 0): l = queries[0] r = queries[1] c += 1 print(query(l, r, pre), end=" ") Q -= 1# Driver Codeif __name__ == "__main__": # Given array arr = [12, 11, 16, 8, 2, 5, 1, 3, 256, 1] # Size of the array N = len(arr) # Given queries queries = [[0, 9], [4, 9]] # Size of queries array Q = len(queries) countInRange(arr, N, queries, Q) # this code is contributed by chitranayal. |
C#
// C# program for the above approach using System;using System.Collections.Generic;class GFG{ // Function to check whether // only one bit is set or not static int check(int x) { if (((x) & (x - 1)) == 0) return 1; return 0; } // Function to perform Range-query static int query(int l, int r, int[] pre) { if (l == 0) return pre[r]; else return pre[r] - pre[l - 1]; } // Function to count array elements with a // single set bit for each range in a query static void countInRange(int[] arr, int N, List<Tuple<int, int>> queries, int Q) { // Initialize array for Prefix sum int[] pre = new int[N]; pre[0] = check(arr[0]); for(int i = 1; i < N; i++) { pre[i] = pre[i - 1] + check(arr[i]); } int c = 0; int q = 0; while (q < Q) { int l = queries[q].Item1; int r = queries[q].Item2; c++; q++; Console.Write(query(l, r, pre) + " "); } } // Driver codestatic void Main() { // Given array int[] arr = { 12, 11, 16, 8, 2, 5, 1, 3, 256, 1 }; // Size of the array int N = arr.Length; // Given queries List<Tuple<int, int>> queries = new List<Tuple<int, int>>(); queries.Add(new Tuple<int, int>(0, 9)); queries.Add(new Tuple<int, int>(4, 9)); // Size of queries array int Q = queries.Count; countInRange(arr, N, queries, Q); }}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// JavaScript program for the above approach// Function to check whether// only one bit is set or notfunction check(x){ if (((x) & (x - 1)) == 0) return 1; return 0;}// Function to perform Range-queryfunction query(l, r, pre){ if (l == 0) return pre[r]; else return pre[r] - pre[l - 1];}// Function to count array elements with a// single set bit for each range in a queryfunction countInRange(arr, N, queries, Q){ // Initialize array for Prefix sum var pre = Array(N).fill(0); pre[0] = check(arr[0]); for (var i = 1; i < N; i++) { pre[i] = pre[i - 1] + check(arr[i]); } var c = 0; while (Q--) { var l = queries[0]; var r = queries[1]; c++; document.write( query(l, r, pre) + ' '); }}// Driver Code// Given arrayvar arr = [12, 11, 16, 8, 2, 5, 1, 3, 256, 1];// Size of the arrayvar N = arr.length;// Given queriesvar queries = [[0, 9], [4, 9 ]]; // Size of queries arrayvar Q = queries.length;countInRange(arr, N, queries, Q);</script> |
Output:
6 4
Time Complexity: O(N*log(max(arr[i])))
Auxiliary Space: O(N)
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!