Given a binary array and Q queries. Every query consists of a number K, the task is to print the number of ones and zeros to the left of the index K.
Examples:
Input: arr[] = {1, 1, 1, 0, 0, 1, 0, 1, 1}, Q[] = {0, 1, 2, 4}
Output:
0 ones 0 zeros
1 ones 0 zeros
2 ones 0 zeros
3 ones 1 zeros
Input: arr[] = {1, 0, 1, 0, 1, 1}, Q[] = {2, 3}
Output:
1 ones 1 zeros
2 ones 1 zeros
Approach: The following steps can be followed to solve the above problem:
- Declare an array of pairs(say left[]) which will be used to pre-calculate the number of ones and zeros to the left.
- Iterate on the array and in every step initialize left[i] with the number of ones and zeros to the left.
- The number of ones for every query will be left[k].first and number of zeros will be left[k].second
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to pre-calculate the left[] arrayvoid preCalculate(int binary[], int n, pair<int, int> left[]){ int count1 = 0, count0 = 0; // Iterate in the binary array for (int i = 0; i < n; i++) { // Initialize the number // of 1 and 0 left[i].first = count1; left[i].second = count0; // Increase the count if (binary[i]) count1++; else count0++; }}// Driver codeint main(){ int binary[] = { 1, 1, 1, 0, 0, 1, 0, 1, 1 }; int n = sizeof(binary) / sizeof(binary[0]); pair<int, int> left[n]; preCalculate(binary, n, left); // Queries int queries[] = { 0, 1, 2, 4 }; int q = sizeof(queries) / sizeof(queries[0]); // Solve queries for (int i = 0; i < q; i++) cout << left[queries[i]].first << " ones " << left[queries[i]].second << " zeros\n"; return 0;} |
Java
// Java implementation of the approachclass GFG { // pair class static class pair { int first, second; pair(int a, int b) { first = a; second = b; } } // Function to pre-calculate the left[] array static void preCalculate(int binary[], int n, pair left[]) { int count1 = 0, count0 = 0; // Iterate in the binary array for (int i = 0; i < n; i++) { // Initialize the number // of 1 and 0 left[i].first = count1; left[i].second = count0; // Increase the count if (binary[i] != 0) count1++; else count0++; } } // Driver code public static void main(String args[]) { int binary[] = { 1, 1, 1, 0, 0, 1, 0, 1, 1 }; int n = binary.length; pair left[] = new pair[n]; for (int i = 0; i < n; i++) left[i] = new pair(0, 0); preCalculate(binary, n, left); // Queries int queries[] = { 0, 1, 2, 4 }; int q = queries.length; // Solve queries for (int i = 0; i < q; i++) System.out.println(left[queries[i]].first + " ones " + left[queries[i]].second + " zeros\n"); }}// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approach# Function to pre-calculate the left[] arraydef preCalculate(binary, n, left): count1, count0 = 0, 0 # Iterate in the binary array for i in range(n): # Initialize the number # of 1 and 0 left[i][0] = count1 left[i][1] = count0 # Increase the count if (binary[i]): count1 += 1 else: count0 += 1# Driver codebinary = [1, 1, 1, 0, 0, 1, 0, 1, 1]n = len(binary)left = [[ 0 for i in range(2)] for i in range(n)]preCalculate(binary, n, left)queries = [0, 1, 2, 4 ]q = len(queries)# Solve queriesfor i in range(q): print(left[queries[i]][0], "ones", left[queries[i]][1], "zeros")# This code is contributed # by mohit kumar |
C#
// C# implementation of the approachusing System;class GFG { // pair class public class pair { public int first, second; public pair(int a, int b) { first = a; second = b; } } // Function to pre-calculate the left[] array static void preCalculate(int[] binary, int n, pair[] left) { int count1 = 0, count0 = 0; // Iterate in the binary array for (int i = 0; i < n; i++) { // Initialize the number // of 1 and 0 left[i].first = count1; left[i].second = count0; // Increase the count if (binary[i] != 0) count1++; else count0++; } } // Driver code public static void Main(String[] args) { int[] binary = { 1, 1, 1, 0, 0, 1, 0, 1, 1 }; int n = binary.Length; pair[] left = new pair[n]; for (int i = 0; i < n; i++) left[i] = new pair(0, 0); preCalculate(binary, n, left); // Queries int[] queries = { 0, 1, 2, 4 }; int q = queries.Length; // Solve queries for (int i = 0; i < q; i++) Console.WriteLine(left[queries[i]].first + " ones " + left[queries[i]].second + " zeros\n"); }}// This code contributed by Rajput-Ji |
PHP
<?php// PHP implementation of the approach // Function to pre-calculate the left[] array function preCalculate($binary, $n) { $left = array(); $count1 = 0; $count0 = 0; // Iterate in the binary array for ($i = 0; $i < $n; $i++) { // Initialize the number // of 1 and 0 $left[$i] = array($count1, $count0); // Increase the count if ($binary[$i]) $count1++; else $count0++; } return $left;} // Driver code $binary = array( 1, 1, 1, 0, 0, 1, 0, 1, 1 ); $n = count($binary);$left = preCalculate($binary, $n); // Queries $queries = array( 0, 1, 2, 4 ); $q = count($queries);// Solve queries for ($i = 0; $i < $q; $i++) echo $left[$queries[$i]][0], " ones ", $left[$queries[$i]][1], " zeros\n"; // This code is contributed by Ryuga ?> |
Javascript
<script>// Javascript implementation of the approach// Function to pre-calculate the left[] array function preCalculate(binary,n,left){ let count1 = 0, count0 = 0; // Iterate in the binary array for (let i = 0; i < n; i++) { // Initialize the number // of 1 and 0 left[i][0] = count1; left[i][1] = count0; // Increase the count if (binary[i] != 0) count1++; else count0++; }}// Driver codelet binary=[1, 1, 1, 0, 0, 1, 0, 1, 1];let n = binary.length;let left=new Array(n); for (let i = 0; i < n; i++) left[i] = [0, 0]; preCalculate(binary, n, left); // Queries let queries = [ 0, 1, 2, 4 ]; let q = queries.length; // Solve queries for (let i = 0; i < q; i++) document.write(left[queries[i]][0] + " ones " + left[queries[i]][1] + " zeros<br>");// This code is contributed by unknown2108</script> |
Output:
0 ones 0 zeros 1 ones 0 zeros 2 ones 0 zeros 3 ones 1 zeros
Time Complexity: O(N+q), as for pre-computation will take O(N) time because we are using a loop to traverse N times and O(1) for every query so total time will be O(q).
Auxiliary Space: O(N), as we are using extra space for the array left.
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!
