Geek has N packs of goodies and the quantity of goodies in every pack is given in an array arr[]. His sister desires to have a pack of chocolate. Geeks being grasping will choose the packs with extra variety of goodies however he can choose from both first or final. Discover the variety of goodies his sister will get.
Examples:
Enter: arr[ ] = {5, 3, 1, 6, 9}
Output: 1
Clarification: Geek may have the packs with goodies
5, 3, 6, 9.Enter: arr[ ] = {5, 9, 2, 6}
Output: Â 2
Strategy: The issue will be solved utilizing the next statement:
As Geek is choosing chocolate packs greedily, so he can at all times be sure that the pack with the minimal variety of goodies is left on the finish.
Comply with the under steps to implement the concept:
- Declare a variable (say ans) and initialize ans = arr[0] to retailer the minimal variety of goodies.
- Iterate from i = 1 to N-1:
- If the worth of arr[i] is lower than ans, replace ans = arr[i].
- The ultimate worth saved in ans would be the minimal worth. So return ans because the required reply.
Under is the implementation of the above method.
C++
|
|
Time Complexity: O(N) As we’re traversing the array as soon as
Auxiliary Area: O(1) As we aren’t utilizing any further house.
