Algorithms · Question 10 · Medium
Algorithms question 10
Coins of value ₹1, ₹3 and ₹4 are available in unlimited supply. A greedy algorithm always picks the largest coin that fits. For an amount of ₹6, what does greedy produce?
- 2 coins, which is optimal
- 3 coins, which is optimal
- 3 coins, which is not optimal (2 coins suffice)
- 4 coins, which is not optimal (2 coins suffice)
Answer and explanation
Answer: C. 3 coins, which is not optimal (2 coins suffice)
Explanation: Greedy picks 4, then 1, then 1, using 3 coins. The optimum is 3 + 3, using 2 coins, so greedy fails for this coin system.
Previous: What does the following function return for f(4096)? · Next: Insertion sort is applied to [5, 2, 4, 6, 1, 3]. What does the array look like…
Practise algorithms
Try a fresh set of algorithms questions with an explanation after every answer, free and without signing up: Algorithms practice. Or sit a full placement mock test.
More algorithms questions
- What is the maximum number of swaps selection sort performs on an array of n…
- Quick sort always picks the last element as the pivot. For which input does it…
- What does the following function return for f(4096)?
- Insertion sort is applied to [5, 2, 4, 6, 1, 3]. What does the array look like…
- What is the length of the Longest Common Subsequence (LCS) of the strings…
- A 0/1 knapsack has capacity 7 kg. The items (weight, value) are: (1 kg, ₹1)…
- For the naive recursive Fibonacci function below, how many times is fib called…
- Using the Master theorem, what is the solution of T(n) = 3T(n/2) + n?
- What is the best-case time complexity of linear search on an array of n…
- Which of the following sorting algorithms is stable in its standard…
More technical & programming practice
Object-Oriented Programming · DBMS · SQL · Operating Systems · Computer Networks · Software Engineering · Cloud & DevOps · GenAI Basics
LogicWiz Exams home · All practice topics · Placement mock tests · Daily 10 challenge