Find the minimum number of operations.

Revision en1, by silentknight00, 2020-03-24 15:47:02

Problem Statement Given a list of array of numbers A,pick the smallest non-negative (≥ 0) then decreases each number of the array by the index of the selected number. This constitutes as one operation. What is the minimum number of operations to do till all kick powers become less than 0? Constraint 1<=Size of Array<=100 1<=Each Element<=1000

I was thinking of the following approach. Store the element's index in an array of size 100x1000(to handle duplicates) Sort the original array. (Nlogn) Iterate over the array with a pointer and maintain a sum of indexes so far and i) check if the current pointer has element less than 0 if yes then move on else ans+=1 and sum of index+=index of the current number(original index)

Is this optimized space and time complexity wise?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English silentknight00 2020-03-24 17:15:51 0 (published)
en2 English silentknight00 2020-03-24 16:54:59 11 Tiny change: ' till all kick powers become le' -> ' till all become le' (saved to drafts)
en1 English silentknight00 2020-03-24 15:47:02 836 Initial revision (published)