NoobCoder1998's blog

Help needed in a problem

By NoobCoder1998, history, 15 months ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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)) + 1

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks 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?

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like 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

      → Reply