Given a binary array a[] of size N and an integer X. All the values of the array are 0 except at index X i.e. a[X] = 1. Given another array of pair v[][] of size M denoting M sequential operations performed in the array. In ith operation, all the values lying in indices [ v[i][0], v[i][1] ] are changed to 1 if there was at least one 1 in that range. Find the total count of 1s after performing these operations sequentially.
Examples:
Input: v[][] = {{1, 6}, {2, 3}, {5, 5}}, N = 6, X = 4
Output: 6
Explanation: Initially the range of elements that can be 1 is [3, 3]. The array is {0, 0, 1, 0, 0, 0}
After the first operation – there is 1 in the given range [1, 6]. So array becomes {1, 1, 1, 1, 1, 1}
After the second operation and third operation the array will be same.
So total number of 1s are 6.Input: v[][] = {{2, 4}, {1, 2}}, N = 4, X = 1
Output: 2
Explanation: Initially the range of the elements that can be 1 is [1, 1]. The array is {1, 0, 0, 0}.
After the first operation – there is no 1 in [2, 4]. So, the array will be {1, 0, 0, 0}.
After the second operation – there is one 1 in [1, 2]. So, the array will be {1, 1, 0, 0}
So, total number of indices that can have 1 is 2.
Approach: Consider the current range to be [L, R]. Initially, The range [L, R] equals [X, X], because initially, only the Xth position is 1. Now, iterate through each of the given ranges, there can be 2 possibilities.
- The current range [L, R] is intersecting with the ith range, Update the current range [L, R] equals [min(L, b[i][0]), max(b[i][1])).
- The current range [L, R] is not intersecting with the ith range, no operation will be performed in this case.
The final answer will be R-L+1. Follow the steps below to solve the problem:
- Initialize the variables L and R as X.
- Iterate over the range [0, M) using the variable i and perform the following steps:
- If l is less than equal to v[i].second and R is greater than equal to v[i][0], then set the values of L as the minimum of L or v[i][0] and R as the maximum of R or v[i][1].
- After performing the above steps, print the value of (R – L + 1) as the answer.
Below is the implementation for the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find Maximum number// of indices with value equal to 1void MaxCount(int N, int X, int M, vector<pair<int, int> >& v){ int L, R; // Initially current range [L, R] = [X, X] L = X, R = X; for (int i = 0; i < M; i++) { // If current range [L, R] and // ith range are intersecting then // update the current range // [L, R] = [min(L, b[i][0]), // max(b[i][1]))] if (L <= v[i].second && v[i].first <= R) { L = min(L, v[i].first); R = max(R, v[i].second); } } // Calculating the answer int ans = R - L + 1; // Printing the maximum number of // indices which can be made 1 // by some flip operations cout << ans;}// Driver Codeint main(){ int N, X, M; N = 6, X = 4, M = 3; vector<pair<int, int> > v = { { 1, 6 }, { 2, 3 }, { 5, 5 } }; MaxCount(N, X, M, v); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to find Maximum number // of indices with value equal to 1 public static void MaxCount(int N, int X, int M, int[][] v) { int L, R; // Initially current range [L, R] = [X, X] L = X; R = X; for (int i = 0; i < M; i++) { // If current range [L, R] and // ith range are intersecting then // update the current range // [L, R] = [min(L, b[i][0]), // max(b[i][1]))] if (L <= v[i][1] && v[i][0] <= R) { L = Math.min(L, v[i][0]); R = Math.max(R, v[i][1]); } } // Calculating the answer int ans = R - L + 1; // Printing the maximum number of // indices which can be made 1 // by some flip operations System.out.println(ans); } // Driver Code public static void main(String[] args) { int N = 6, X = 4, M = 3; int[][] v = new int[][] { { 1, 6 }, { 2, 3 }, { 5, 5 } }; MaxCount(N, X, M, v); }}// This code is contributed by rakeshsahni |
Python3
# Python code for the above approach# Function to find Maximum number# of indices with value equal to 1def MaxCount(N, X, M, v): # Initially current range [L, R] = [X, X] L = X R = X for i in range(M): # If current range [L, R] and # ith range are intersecting then # update the current range # [L, R] = [min(L, b[i][0]), # max(b[i][1]))] if (L <= v[i]["second"] and v[i]["first"] <= R): L = min(L, v[i]["first"]) R = max(R, v[i]["second"]) # Calculating the answer ans = R - L + 1 # Printing the maximum number of # indices which can be made 1 # by some flip operations print(ans)# Driver CodeN = 6X = 4M = 3v = [{"first": 1, "second": 6}, {"first": 2, "second": 3}, {"first": 5, "second": 5}]MaxCount(N, X, M, v)# This code is contributed by Saurabh Jaiswal |
C#
// C# code for the above approachusing System;class GFG { // Function to find Maximum number // of indices with value equal to 1 static void MaxCount(int N, int X, int M, int[, ] v) { // Initially current range [L, R] = [X, X] int L = X, R = X; for (int i = 0; i < M; i++) { // If current range [L, R] and // ith range are intersecting then // update the current range // [L, R] = [min(L, b[i][0]), // max(b[i][1]))] if (L <= v[i, 1] && v[i, 0] <= R) { L = Math.Min(L, v[i, 0]); R = Math.Max(R, v[i, 1]); } } // Calculating the answer int ans = R - L + 1; // Printing the maximum number of // indices which can be made 1 // by some flip operations Console.Write(ans); } // Driver Code public static int Main() { int N = 6, X = 4, M = 3; int[, ] v = new int[, ] { { 1, 6 }, { 2, 3 }, { 5, 5 } }; MaxCount(N, X, M, v); return 0; }}// This code is contributed by Taranpreet |
Javascript
<script> // JavaScript code for the above approach // Function to find Maximum number // of indices with value equal to 1 function MaxCount(N, X, M, v) { let L, R; // Initially current range [L, R] = [X, X] L = X, R = X; for (let i = 0; i < M; i++) { // If current range [L, R] and // ith range are intersecting then // update the current range // [L, R] = [min(L, b[i][0]), // max(b[i][1]))] if (L <= v[i].second && v[i].first <= R) { L = Math.min(L, v[i].first); R = Math.max(R, v[i].second); } } // Calculating the answer let ans = R - L + 1; // Printing the maximum number of // indices which can be made 1 // by some flip operations document.write(ans) } // Driver Code let N, X, M; N = 6, X = 4, M = 3; let v = [{ first: 1, second: 6 }, { first: 2, second: 3 }, { first: 5, second: 5 }]; MaxCount(N, X, M, v); // This code is contributed by Potta Lokesh </script> |
6
Time Complexity: O(M), as we are using a loop to traverse M times so it will cost us O(M) time
Auxiliary Space: O(1), as we are not using any extra space.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
