Given a strictly increasing array A[] of size N, an integer K and Q queries of type [L, R], the task is to count the number of ways such that the subarray from L to R remains strictly increasing when only one replacement is performed and all the elements will be in the range [1, K].
Examples:
Input: A[] = {1, 2, 4, 5}, K = 5, Q = 2, Queries[][] = {{1, 2}, {2, 3}}
Output: 4 3
Explanation: For Query1 – subarray [2, 4].
The ways will be [1, 4] [3, 4] (only 1st position is replaced), and
[2, 3] [2, 5] (only 2nd position is changed). So number of ways are 4.
For Query2 – subarray [4, 5].
The ways are [1, 5] [2, 5] [3, 5] (only 1st position is replaced).
Second position cannot be replaced as is already 5 which is equal to K
and the previous element is 4. There does not exist any element in between.
So number of ways are 3.Input: A[] = {1, 3, 4}, K = 4, Q = 1, Queries = {{0, 2}}
Output: 2
Approach: The problem can be solved based on the following idea:
We need to calculate the possible changes for every element in each query so here pre-computed values can save an extra iteration of N for each query separately and each query can be answered in O(1) using the precomputed values in prefix sum.
Follow the following steps to answer each query in constant time.
- Precompute that if ith element is replaced then how many possibilities are there and store it in an array (say pre [ ]).
- A[i] can be replaced by all the elements in the range (A[i-1], A[i+1]) except for A[i] itself. So number of ways = A[i+1] – A[i-1] – 2.
- Calculate the prefix sum in pre[] to store the number of possible ways where pre[i] denotes possible ways from 0 to i.
- Now using prefix sum array we can answer each query by using pre [R] – pre[L – 1].
- But can replace the element at L index with elements from 1 to a[L + 1] – 1 and element at R index from a[R] + 1 to K as the subarray L to R should be sorted by replacing exactly one element.
- So add A[L + 1] – 2 for the position L.
- Similarly, for the last element, add (K – (A[R – 1] + 1)) as the element at position R can begin from A[R – 1] + 1 and go till K.
- Then add all of these different parts and return the final answer.
Below is the implementation of the above approach.
C++14
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Array to store precomputed valuesint pre[100005];// Function to fill pre arrayvoid precompute(int a[], int N){ for (int i = 0; i < N; i++) { if (i == 0) { // First element can be replaced // with every element smaller than // next element except itself pre[i] = a[1] - 2; } else { // If this is not the last element if (i != N - 1) { // Calculate possible values for // the current index that it can // be replaced with pre[i] = a[i + 1] - a[i - 1] - 2; } } } for (int i = 1; i < N; i++) { // Calculating prefix sum pre[i] += pre[i - 1]; }}// Function to answer the queriesvoid solve(int Q, int Queries[2][2], int K, int a[], int N){ // Precomputing values only if there is // more than one element if (N > 1) { // Function call precompute(a, N); } // Loop for answering queries for (int i = 0; i < Q; i++) { // Taking L and R from Queries int L = Queries[i][0]; int R = Queries[i][1]; if (L == R) { // if single element subarray then // it can be replaced with K - 1 // elements cout << K - 1 << " "; } else { int ans = 0; // Possible replacements for // element at index L int left = a[L + 1] - 1; ans += (left - 1); // Possible replacements for // element at index R int right = a[R - 1] + 1; ans += (K - right); // Possible replacements for // element in range [L + 1, R - 1] ans += (pre[R - 1] - pre[L]); // Printing the answer cout << ans << " "; } }}// Driver Codeint main(){ int A[] = { 1, 2, 4, 5 }; int N = sizeof(A) / sizeof(A[0]); int Q = 2, K = 5; int Queries[Q][2] = { { 1, 2 }, { 2, 3 } }; // Function call solve(Q, Queries, K, A, N); return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Array to store precomputed values static int pre[] = new int[100005]; // Function to fill pre array public static void precompute(int a[], int N) { for (int i = 0; i < N; i++) { if (i == 0) { // First element can be replaced // with every element smaller than // next element except itself pre[i] = a[1] - 2; } else { // If this is not the last element if (i != N - 1) { // Calculate possible values for // the current index that it can // be replaced with pre[i] = a[i + 1] - a[i - 1] - 2; } } } for (int i = 1; i < N; i++) { // Calculating prefix sum pre[i] += pre[i - 1]; } } // Function to answer the queries public static void solve(int Q, int Queries[][], int K, int a[], int N) { // Precomputing values only if there is // more than one element if (N > 1) { // Function call precompute(a, N); } // Loop for answering queries for (int i = 0; i < Q; i++) { // Taking L and R from Queries int L = Queries[i][0]; int R = Queries[i][1]; if (L == R) { // if single element subarray then // it can be replaced with K - 1 // elements System.out.print(K - 1 + " "); } else { int ans = 0; // Possible replacements for // element at index L int left = a[L + 1] - 1; ans += (left - 1); // Possible replacements for // element at index R int right = a[R - 1] + 1; ans += (K - right); // Possible replacements for // element in range [L + 1, R - 1] ans += (pre[R - 1] - pre[L]); // Printing the answer System.out.print(ans + " "); } } } // Driver Code public static void main(String[] args) { int A[] = { 1, 2, 4, 5 }; int N = A.length; int Q = 2, K = 5; int Queries[][] = { { 1, 2 }, { 2, 3 } }; // Function call solve(Q, Queries, K, A, N); }}// This code is contributed by Rohit Pradhan |
Python3
# Python code to implement the approach# list to store precomputed valuespre = [0]*100005# Function to fill pre arraydef precompute(a, N): for i in range(N): if (i == 0): # First element can be replaced # with every element smaller than # next element except itself pre[i] = a[1] - 2 else: # If this is not the last element if (i != N - 1): # Calculate possible values for # the current index that it can # be replaced with pre[i] = a[i + 1] - a[i - 1] - 2 for i in range(1, N): # Calculating prefix sum pre[i] += pre[i - 1] # Function to answer the queriesdef solve(Q, Queries, K, a, N): # Precomputing values only if there is # more than one element if (N > 1): # Function call precompute(a, N) # Loop for answering queries for i in range(Q): # Taking L and R from Queries L = Queries[i][0] R = Queries[i][1] if (L == R): # if single element subarray then # it can be replaced with K - 1 # elements print(K - 1, end = " ") else: ans = 0 # Possible replacements for # element at index L left = a[L + 1] - 1 ans += (left - 1) # Possible replacements for # element at index R right = a[R - 1] + 1 ans += (K - right) # Possible replacements for # element in range [L + 1, R - 1] ans += (pre[R - 1] - pre[L]) # Printing the answer print(ans , end = " ") # Driver CodeA = [1, 2, 4, 5]N = len(A)Q = 2K = 5Queries = [[1, 2 ], [2, 3]]# Function callsolve(Q, Queries, K, A, N)# This code is contributed by Atul_kumar_shrivastava. |
C#
// C# code for the above approachusing System;using System.Collections.Generic;class GFG { // Array to store precomputed values static int[] pre = new int[100005]; // Function to fill pre array public static void precompute(int[] a, int N) { for (int i = 0; i < N; i++) { if (i == 0) { // First element can be replaced // with every element smaller than // next element except itself pre[i] = a[1] - 2; } else { // If this is not the last element if (i != N - 1) { // Calculate possible values for // the current index that it can // be replaced with pre[i] = a[i + 1] - a[i - 1] - 2; } } } for (int i = 1; i < N; i++) { // Calculating prefix sum pre[i] += pre[i - 1]; } } // Function to answer the queries public static void solve(int Q, int[,] Queries, int K, int[] a, int N) { // Precomputing values only if there is // more than one element if (N > 1) { // Function call precompute(a, N); } // Loop for answering queries for (int i = 0; i < Q; i++) { // Taking L and R from Queries int L = Queries[i, 0]; int R = Queries[i, 1]; if (L == R) { // if single element subarray then // it can be replaced with K - 1 // elements Console.Write(K - 1 + " "); } else { int ans = 0; // Possible replacements for // element at index L int left = a[L + 1] - 1; ans += (left - 1); // Possible replacements for // element at index R int right = a[R - 1] + 1; ans += (K - right); // Possible replacements for // element in range [L + 1, R - 1] ans += (pre[R - 1] - pre[L]); // Printing the answer Console.Write(ans + " "); } } }// Driver Codepublic static void Main(){ int[] A = { 1, 2, 4, 5 }; int N = A.Length; int Q = 2, K = 5; int[,] Queries = { { 1, 2 }, { 2, 3 } }; // Function call solve(Q, Queries, K, A, N);}}// This code is contributed by sanjoy_62. |
Javascript
<script>// Array to store precomputed valueslet pre = [];for(let i=0;i<100005;i++){ pre[i] = 0;}// Function to fill pre arrayfunction precompute(a,N){ for (let i = 0; i < N; i++) { if (i == 0) { // First element can be replaced // with every element smaller than // next element except itself pre[i] = a[1] - 2; } else { // If this is not the last element if (i != N - 1) { // Calculate possible values for // the current index that it can // be replaced with pre[i] = a[i + 1] - a[i - 1] - 2; } } } for (let i = 1; i < N; i++) { // Calculating prefix sum pre[i] += pre[i - 1]; }}// Function to answer the queriesfunction solve( Q,Queries, K, a,N){ // output to be printed let output = ""; // Precomputing values only if there is // more than one element if (N > 1) { // Function call precompute(a, N); } // Loop for answering queries for (let i = 0; i < Q; i++) { // Taking L and R from Queries let L = Queries[i][0]; let R = Queries[i][1]; if (L == R) { // if single element subarray then // it can be replaced with K - 1 // elements let z = K-1; output+=z+" "; } else { let ans = 0; // Possible replacements for // element at index L let left = a[L + 1] - 1; ans += (left - 1); // Possible replacements for // element at index R let right = a[R - 1] + 1; ans += (K - right); // Possible replacements for // element in range [L + 1, R - 1] ans += (pre[R - 1] - pre[L]); // Printing the answer output+=ans+" "; } } console.log(output);}// Driver codelet A = [ 1, 2, 4, 5 ];let N = A.length;let Q = 2, K = 5;let Queries = [ [ 1, 2 ], [ 2, 3 ] ];// Function callsolve(Q, Queries, K, A, N);// This code is contributed by akashish__</script> |
Output
4 3
Time Complexity: O(N + Q)
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!
Share your thoughts in the comments
