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-increasingint 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 codeint 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 approachimport 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-increasingdef 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 codearr = [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 approachusing 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> |
Output
2
Time Complexity: O(K * N * logN)
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!
