Given an array arr[] of N positive integers and an integer K, The task is to replace minimum number of elements with any positive integer to make the array K-increasing. An array is K-increasing if for every index i in range [K, N), arr[i] ≥ arr[i-K]
Examples:
Input: arr[] = {4, 1, 5, 2, 6, 2}, k = 2
Output: 0
Explanation: Here, for every index i where 2 <= i <= 5, arr[i-2] <= arr[i]
Since the given array is already K-increasing, there is no need to perform any operations.Input: arr[] = {4, 1, 5, 2, 6, 2}, k = 3
Output: 2
Explanation: Indices 3 and 5 are the only ones not satisfying arr[i-3] <= arr[i] for 3 <= i <= 5.
One of the ways we can make the array K-increasing is by changing arr[3] to 4 and arr[5] to 5.
The array will now be [4,1,5,4,6,5].
Approach: This solution is based on finding the longest increasing subsequence. Since the above question requires that arr[i-K] ≤ arr[i] should hold for every index i, where K ≤ i ≤ N-1, here the importance is given to compare the elements which are K places away from each other.
So the task is to confirm that the sequences formed by the elements K places away are all non decreasing in nature. If they are not then perform the replacements to make them non-decreasing.
Follow the steps mentioned below:
- Traverse the array and form sequence(seq[]) by picking elements K places away from each other in the given array.
- Check if all the elements in seq[] is non-decreasing or not.
- If not then find the length of longest non-decreasing subsequence of seq[].
- Replace the remaining elements to minimize the total number of operations.
- Sum of replacement operations for all such sequences is the final answer.
Follow the below illustration for better understanding.
• For example: arr[] = {4, 1, 5, 2, 6, 0, 1} ,K = 2
Indices: 0 1 2 3 4 5 6
values: 4 1 5 2 6 0 1So the work is to ensure that following sequences
- arr[0], arr[2], arr[4], arr[6] => {4, 5, 6, 1}
- arr[1], arr[3], arr[5] => {1, 2, 0}
Obey arr[i-k] <= arr[i]
So for first sequence it can be seen that {4, 5, 6} are K increasing and it is the longest non-decreasing subsequence, whereas 1 is not, so one operation is needed for it.
Similarly, for 2nd {1, 2} are longest non-decreasing whereas 0 is not, so one operation is needed for it.So total 2 minimum operations are required.
Below is the implementation of the above approach.
C++
// C++ code to implement above approach #include <bits/stdc++.h> using namespace std; // Functions finds the // longest non decreasing subsequence. int utility(vector< int >& arr, int & n) { vector< int > tail; int len = 1; tail.push_back(arr[0]); for ( int i = 1; i < n; i++) { if (tail[len - 1] <= arr[i]) { len++; tail.push_back(arr[i]); } else { auto it = upper_bound(tail.begin(), tail.end(), arr[i]); *it = arr[i]; } } return len; } // Function to find the minimum operations // to make array K-increasing int kIncreasing(vector< int >& a, int K) { int ans = 0; // Size of array int N = a.size(); for ( int i = 0; i < K; i++) { // Consider all elements K-places away // as a sequence vector< int > v; for ( int j = i; j < N; j += K) { v.push_back(a[j]); } // Size of each sequence int k = v.size(); // Store least operations // for this sequence ans += k - utility(v, k); } return ans; } // Driver code int main() { vector< int > arr{ 4, 1, 5, 2, 6, 0, 1 }; int K = 2; cout << kIncreasing(arr, K); return 0; } |
Java
// Java code for the above approach import java.util.ArrayList; class GFG { static int lowerBound(ArrayList<Integer> a, int low, int high, int element) { while (low < high) { int middle = low + (high - low) / 2 ; if (element > a.get(middle)) low = middle + 1 ; else high = middle; } return low; } static int utility(ArrayList<Integer> v, int n) { if (v.size() == 0 ) // boundary case return 0 ; int [] tail = new int [v.size()]; int length = 1 ; // always points empty slot in tail tail[ 0 ] = v.get( 0 ); for ( int i = 1 ; i < v.size(); i++) { if (v.get(i) > tail[length - 1 ]) { // v[i] extends the largest subsequence tail[length++] = v.get(i); } else { // v[i] will extend a subsequence and // discard older subsequence // find the largest value just smaller than // v[i] in tail // to find that value do binary search for // the v[i] in the range from begin to 0 + // length var idx = lowerBound(v, 1 , v.size(), v.get(i)); // binarySearch in C# returns negative // value if searched element is not found in // array // this negative value stores the // appropriate place where the element is // supposed to be stored if (idx < 0 ) idx = - 1 * idx - 1 ; // replacing the existing subsequence with // new end value tail[idx] = v.get(i); } } return length; } // Function to find the minimum operations // to make array K-increasing static int kIncreasing( int [] a, int K) { int ans = 0 ; // Size of array int N = a.length; for ( int i = 0 ; i < K; i++) { // Consider all elements K-places away // as a sequence ArrayList<Integer> v = new ArrayList<Integer>(); for ( int j = i; j < N; j += K) { v.add(a[j]); } // Size of each sequence int k = v.size(); // Store least operations // for this sequence ans += k - utility(v, k); } return ans; } // Driver code public static void main(String args[]) { int [] arr = { 4 , 1 , 5 , 2 , 6 , 0 , 1 }; int K = 2 ; System.out.println(kIncreasing(arr, K)); } } // This code is contributed by Saurabh Jaiswal. |
Python3
# Python code for the above approach def lowerBound(a, low, high, element): while (low < high): middle = low + (high - low) / / 2 ; if (element > a[middle]): low = middle + 1 ; else : high = middle; return low; def utility(v): if ( len (v) = = 0 ): # boundary case return 0 ; tail = [ 0 ] * len (v) length = 1 ; # always points empty slot in tail tail[ 0 ] = v[ 0 ]; for i in range ( 1 , len (v)): if (v[i] > tail[length - 1 ]): # v[i] extends the largest subsequence length + = 1 tail[length] = v[i]; else : # v[i] will extend a subsequence and # discard older subsequence # find the largest value just smaller than # v[i] in tail # to find that value do binary search for # the v[i] in the range from begin to 0 + # length idx = lowerBound(v, 1 , len (v), v[i]); # binarySearch in C# returns negative # value if searched element is not found in # array # this negative value stores the # appropriate place where the element is # supposed to be stored if (idx < 0 ): idx = - 1 * idx - 1 ; # replacing the existing subsequence with # new end value tail[idx] = v[i]; return length; # Function to find the minimum operations # to make array K-increasing def kIncreasing(a, K): ans = 0 ; # Size of array N = len (a) for i in range (K): # Consider all elements K-places away # as a sequence v = []; for j in range (i, N, K): v.append(a[j]); # Size of each sequence k = len (v); # Store least operations # for this sequence ans + = k - utility(v); return ans; # Driver code arr = [ 4 , 1 , 5 , 2 , 6 , 0 , 1 ]; K = 2 ; print (kIncreasing(arr, K)); # This code is contributed by gfgking |
C#
// C# code for the above approach using System; using System.Collections.Generic; class GFG { static int lowerBound(List< int > a, int low, int high, int element) { while (low < high) { int middle = low + (high - low) / 2; if (element > a[middle]) low = middle + 1; else high = middle; } return low; } static int utility(List< int > v, int n) { if (v.Count == 0) // boundary case return 0; int [] tail = new int [v.Count]; int length = 1; // always points empty slot in tail tail[0] = v[0]; for ( int i = 1; i < v.Count; i++) { if (v[i] > tail[length - 1]) { // v[i] extends the largest subsequence tail[length++] = v[i]; } else { // v[i] will extend a subsequence and // discard older subsequence // find the largest value just smaller than // v[i] in tail // to find that value do binary search for // the v[i] in the range from begin to 0 + // length var idx = lowerBound(v, 1, v.Count, v[i]); // binarySearch in C# returns negative // value if searched element is not found in // array // this negative value stores the // appropriate place where the element is // supposed to be stored if (idx < 0) idx = -1 * idx - 1; // replacing the existing subsequence with // new end value tail[idx] = v[i]; } } return length; } // Function to find the minimum operations // to make array K-increasing static int kIncreasing( int [] a, int K) { int ans = 0; // Size of array int N = a.Length; for ( int i = 0; i < K; i++) { // Consider all elements K-places away // as a sequence List< int > v = new List< int >(); for ( int j = i; j < N; j += K) { v.Add(a[j]); } // Size of each sequence int k = v.Count; // Store least operations // for this sequence ans += k - utility(v, k); } return ans; } // Driver code public static void Main() { int [] arr = { 4, 1, 5, 2, 6, 0, 1 }; int K = 2; Console.Write(kIncreasing(arr, K)); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach function lowerBound(a, low, high, element) { while (low < high) { var middle = low + (high - low) / 2; if (element > a[middle]) low = middle + 1; else high = middle; } return low; } function utility(v) { if (v.length == 0) // boundary case return 0; var tail = Array(v.length).fill(0); var length = 1; // always points empty slot in tail tail[0] = v[0]; for (i = 1; i < v.length; i++) { if (v[i] > tail[length - 1]) { // v[i] extends the largest subsequence tail[length++] = v[i]; } else { // v[i] will extend a subsequence and // discard older subsequence // find the largest value just smaller than // v[i] in tail // to find that value do binary search for // the v[i] in the range from begin to 0 + // length var idx = lowerBound(v, 1, v.length, v[i]); // binarySearch in C# returns negative // value if searched element is not found in // array // this negative value stores the // appropriate place where the element is // supposed to be stored if (idx < 0) idx = -1 * idx - 1; // replacing the existing subsequence with // new end value tail[idx] = v[i]; } } return length; } // Function to find the minimum operations // to make array K-increasing function kIncreasing(a, K) { let ans = 0; // Size of array let N = a.length; for (let i = 0; i < K; i++) { // Consider all elements K-places away // as a sequence let v = []; for (let j = i; j < N; j += K) { v.push(a[j]); } // Size of each sequence let k = v.length; // Store least operations // for this sequence ans += k - utility(v, k); } return ans; } // Driver code let arr = [4, 1, 5, 2, 6, 0, 1]; let K = 2; document.write(kIncreasing(arr, K)); // This code is contributed by Potta Lokesh </script> |
2
Time Complexity: O(K * N * logN)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!