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++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find tastiness level// of the square that his sister getsint chocolates(int arr[], int n){ int ans = arr[0]; // Loop to find the minimum element for (int i = 1; i < n; i++) { if (arr[i] < ans) { ans = arr[i]; } } // Return the answer return ans;}// Driver Codeint main(){ int arr[] = { 5, 3, 1, 6, 9 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call cout << chocolates(arr, N) << endl; return 0;} |
Java
// Java code for the above approachimport java.util.*;public class GFG { // Function to find tastiness level // of the square that his sister gets public static int chocolates(int[] arr, int n) { int ans = arr[0]; // Loop to find the minimum element for (int i = 1; i < n; i++) { if (arr[i] < ans) { ans = arr[i]; } } // Return the answer return ans; }// driver codepublic static void main(String[] args){ int[] arr = { 5, 3, 1, 6, 9 }; int N = arr.length; // Function Call System.out.print(chocolates(arr, N));}}// This code is contributed by code_hunt. |
C#
using System;public class GFG { // Function to find tastiness level // of the square that his sister gets public static int chocolates(int[] arr, int n) { int ans = arr[0]; // Loop to find the minimum element for (int i = 1; i < n; i++) { if (arr[i] < ans) { ans = arr[i]; } } // Return the answer return ans; } static public void Main() { int[] arr = { 5, 3, 1, 6, 9 }; int N = arr.Length; // Function Call Console.WriteLine(chocolates(arr, N)); }}// This code is contributed by akashish__ |
Python3
# Python code to implement the approach# Function to find tastiness level# of the square that his sister getsdef chocolates(arr, n): ans = arr[0] # Loop to find the minimum element for i in range(1, n): if (arr[i] < ans): ans = arr[i] # Return the answer return ans# Driver Codeif __name__ == '__main__': arr = [5, 3, 1, 6, 9] N = len(arr) # Function call print(chocolates(arr, N)) # This code is contributed by arohirai2616. |
Javascript
<script>// Javascript code for the above approach// Function to find tastiness level// of the square that his sister getsfunction chocolates(arr,n) { let ans = arr[0]; // Loop to find the minimum element for (let i = 1; i < n; i++) { if (arr[i] < ans) { ans = arr[i]; } } // Return the answer return ans; } // driver code let arr = [ 5, 3, 1, 6, 9 ]; let N = arr.length; // Function Call console.log(chocolates(arr, N));// This code is contributed by arohirai2616.</script> |
PHP
// 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.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
