Given a large binary number.The task is to count the number of 1’s in a given range from L to R (1 based indexing).
Examples:
Input : s = “101101011010100000111”, L = 6, R = 15
Output : 5
s [L : R] = “1011010100”
There is only 5 set bits.
Input : s = “10110”, L = 2, R = 5
Output : 2
Approach:
- Convert the string of size len to the bitset of size N.
- There is no need of (N – len) + (L – 1) bits in the left side and (N – R) bits in the right side of the bitset .
- Remove those bits efficiently using left and right shift bitwise operation.
- Now there are all zeroes in the left side of L and right side of R, so just use count() function to get the count of 1’s in the bitset as all positions except [L, R] are ‘0’.
Below is the implementation of above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;#define N 32// C++ function to count // number of 1's using bitsetint GetOne(string s, int L, int R){ int len = s.length(); // Converting the string into bitset bitset<N> bit(s); // Bitwise operations // Left shift bit <<= (N - len + L - 1); // Right shifts bit >>= (N - len + L - 1); bit >>= (len - R); // Now bit has only those bits // which are in range [L, R] // return count of one in [L, R] return bit.count();}// Driver codeint main(){ string s = "01010001011"; int L = 2, R = 4; cout << GetOne(s, L, R); return 0;} |
Java
// Java implementation of above approachpublic class Main { static final int N = 32; // Function to count // the number of 1's using a bit string static int getOne(String s, int L, int R) { int len = s.length(); // Converting s to an N-bit representation s = "0".repeat(Math.max(0, N - len)) + s; // Extracting bits of the range [L, R] String bit = s.substring(N - R, N - L + 1); // Now bit has only those bits // which are in the range [L, R] // Return the count of '1's in [L, R] return (int) bit.chars().filter(c -> c == '1').count(); } // Driver code public static void main(String[] args) { String s = "01010001011"; int L = 2, R = 4; // Function Call System.out.println(getOne(s, L, R)); }} |
Python3
# Python3 implementation of above approach N = 32# function for converting binary# string into integer valuedef binStrToInt(binary_str): length = len(binary_str) num = 0 for i in range(length): num = num + int(binary_str[i]) num = num * 2 return num / 2# function to count # number of 1's using bitset def GetOne(s, L, R) : length = len(s); # Converting the string into bitset bit = s.zfill(32-len(s)); bit = int(binStrToInt(bit)) # Bitwise operations # Left shift bit <<= (N - length + L - 1); # Right shifts bit >>= (N - length + L - 1); bit >>= (length - R); # Now bit has only those bits # which are in range [L, R] # return count of one in [L, R] return bin(bit).count('1'); # Driver code if __name__ == "__main__" : s = "01010001011"; L = 2; R = 4; print(GetOne(s, L, R)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of above approachusing System;using System.Linq;class GFG { static int N = 32; // C# function to count // number of 1's using bit string static int GetOne(string s, int L, int R) { int len = s.Length; // Converting s to an N bit representation s = s.PadLeft(N, '0'); // Extracting bits of the range [L, R] string bit = s.Substring(N - R, R - L + 1); // Now bit has only those bits // which are in range [L, R] // return count of one in [L, R] return bit.Count(f => (f == '1')); } // Driver code public static void Main(string[] args) { string s = "01010001011"; int L = 2, R = 4; // Function Call Console.WriteLine(GetOne(s, L, R)); }}// This code is contributed by phasing17 |
Javascript
// JavaScript implementation of above approachvar N = 32;// function for converting binary// string into integer valuefunction binStrToInt(binary_str){ var length = binary_str.length; var num = 0; for (var i = 0; i < length; i++) { num = num + parseInt(binary_str[i]); num = num * 2; } return num / 2;}// function to count// number of 1's using bitsetfunction GetOne(s, L, R){ var length = s.length; // Converting the string into bitset var bit = "0" * (32 - length) + s; bit = parseInt(binStrToInt(bit)); // Bitwise operations // Left shift bit <<= (N - length + L - 1); // Right shifts bit >>= (N - length + L - 1); bit >>= (length - R); // Now bit has only those bits // which are in range [L, R] // return count of one in [L, R] return bit.toString(2).split("1").length - 1;}var s = "01010001011";var L = 2;var R = 4;console.log(GetOne(s, L, R));//This code is contributed by phasing17 |
Output
2
Time Complexity: O(len)
Auxiliary Space: O(len)
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!
