Horje
Find minimum chocolates left after following the given rules

Geek has N packs of chocolates and the amount of chocolates in each pack is given in an array arr[]. His sister wants to have a pack of chocolate. Geeks being greedy will pick the packs with more number of chocolates but he can pick from either first or last. Find the number of chocolates his sister will get.

Examples:

Input: arr[ ] = {5, 3, 1, 6, 9}
Output: 1
Explanation: Geek will have the packs with chocolates
5, 3, 6, 9.

Input: arr[ ] = {5, 9, 2, 6}
Output:  2

Approach: The problem can be solved using the following observation:

As Geek is picking chocolate packs greedily, so he can always make sure that the pack with the minimum number of chocolates is left at the end.

Follow the below steps to implement the idea:

  • Declare a variable (say ans) and initialize ans = arr[0] to store the minimum number of chocolates.
  • Iterate from i = 1 to N-1:
    • If the value of arr[i] is less than ans, update ans = arr[i].
  • The final value stored in ans will be the minimum value. So return ans as the required answer.

Below is the implementation of the above approach.

C++

// PHP Code
<?php
    // Function to find tastiness level
    // of the square that his sister gets
    function chocolates($arr, $n) {
        $ans = $arr[0];
 
        // Loop to find the minimum element
        for ($i = 1; $i < $n; $i++) {
            if ($arr[$i] < $ans) {
                $ans = $arr[$i];
            }
        }
 
        // Return the answer
        return $ans;
    }
 
    // Driver Code
    $arr = [5, 3, 1, 6, 9];
    $n = sizeof($arr)/sizeof($arr[0]);
     
    // Function Call
    echo chocolates($arr, $n);
 // This code is contributed by Kanishka Gupta
?>

Output

1

Time Complexity: O(N) As we are traversing the array once
Auxiliary Space: O(1) As we are not using any extra space.


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Why use an Array to implement a &quot;list&quot; instead of a Hash Table? Why use an Array to implement a &quot;list&quot; instead of a Hash Table?
Divide maximum element in N groups so that received and required has difference atmost K Divide maximum element in N groups so that received and required has difference atmost K
Minimum money required to buy items with given cashbacks Minimum money required to buy items with given cashbacks
Maximize X such that Array can be sorted by swapping elements X distance apart Maximize X such that Array can be sorted by swapping elements X distance apart
Maximize the value of (A[i]-A[j])*A[k] for any ordered triplet of indices i, j and k Maximize the value of (A[i]-A[j])*A[k] for any ordered triplet of indices i, j and k

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje