Given an array nums containing N distinct integers and an integer K. You can perform any number of operations:
Select a sub-array of length K in nums and replace all the elements in the sub- array with the maximum number present in the current sub-array.
Find the minimum number of operations such that nums[1]=nums[n].
Input Format
The first line contains an integer N, where N denotes the number of elements in the array in the array. The second line contains N space- separated integers. The third line contains an integer, K.
Output Format
Print the minimum number of operations such that nums[1] nums[n].
Constraints:
•2sN,Ks10^5 • 1s am[i] $10^9
-I tried solving it but not able to find any optimal approach for the same.
Since all elements are distinct then to make nums[1]=nums[n] both will be equal to the max element in the array, so first we will make an operation on a subarray of length k which contains the max element then all elements in that subarray will be equal to the max element, then to make the first element equal to the max we can choose a subarray from l to r and nums[r] is the max element, then elements from l to r-1 will be equal to the max "make new k-1 elements equal to the max", we will do that till we reach nums[1], and the same thing to reach nums[n] but choosing a subarray from l to r and nums[l] is the max element.
so I guess the answer will be
ceil((n-k) / (k-1)) + 1Thanks got it. I missed the fact that elements are distinct that makes it a lot easier. But just in case suppose elements weren't distinct then do we go about solving it?
we will try to get the nearest index to nums[1] "idx1", and nearest index to nums[n] "idx2" such that max(nums[1],nums[2],...,nums[idx1]) = max(nums[idx2],nums[idx2+1],...,nums[n]) and idx1 >= k and n-idx2+1 >= k, then the answer will be
ceil((idx1-k) / (k-1)) + 1 + ceil(((n-idx2+1)-k) / (k-1)) + 1, we iterate through idx1 and by using binary search and suffix max we will get idx2 and minimize the answer every time. but you need to check if it's not neccessary to change the value of nums[1] or the value of nums[n].it makes sense but I am not fully sure if it's optimal