English
Menu

Data Structures and Algorithms

You pay 8 yen with coins of 1 yen, 4 yen and 6 yen. Which correctly relates the number of coins chosen by a greedy algorithm, which uses as many of the largest coin as possible first, to the minimum number of coins?

  1. AThe greedy algorithm also reaches the minimum of 2 coins
  2. BThe greedy algorithm uses 3 coins and misses the minimum of 2
  3. CThe greedy algorithm uses 3 coins, and that is the minimum
Show answer and explanation

Answer: B. The greedy algorithm uses 3 coins and misses the minimum of 2

The greedy algorithm first takes one 6-yen coin and pays the remaining 2 yen with two 1-yen coins, for 3 coins. But two 4-yen coins pay it with just 2. Because a greedy algorithm only accumulates the choice that looks best at each moment, it is not optimal for some coin systems. Dynamic programming, which fills in a table of the minimum number of coins for every amount from 0 to 8 yen in increasing order, always finds the minimum. For coin systems such as Japan's 1, 5, 10, 50, 100 and 500 yen, the greedy algorithm always gives the minimum.

  • A. The greedy algorithm picks the 6-yen coin first, so it never reaches the two-4-yen combination.
  • B. Correct. Greedy gives 6 + 1 + 1, three coins; the minimum is 4 + 4, two coins.
  • C. Two 4-yen coins pay it with 2 coins, so 3 is not the minimum.
Practice this topic Back to topic

Related calculators

Time complexity (Big-O) comparison toolCompare the number of steps and the time for O(log n), O(n), O(n log n), O(n²), O(2ⁿ) and more as the data grows, and estimate the running time for a different data sizeSorting algorithm visualizerWatch 7 sorting algorithms (bubble, selection, insertion, shell, merge, quick and heap) step by step as bar charts, and compare their comparison and write counts

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

More Data Structures and Algorithms questions

  1. A knapsack with capacity 8 is filled with items chosen from four items with (weight, value) of (2, 3), (3, 4), (4, 5) and (5, 6). There is only one of each item and items cannot be split. What is the maximum total value with a total weight of 8 or less?
  2. Which is a characteristic of the Boyer-Moore algorithm for finding a pattern in a string?
  3. A dynamic array, when an element is added while it is full, allocates a new area with twice the capacity and copies all elements into it. If 1,000 elements are added one at a time to an empty array of capacity 1, how many element copies are made in total?
  4. For a hash table with many elements kept at a load factor of about 0.5, which is the most appropriate reason that open addressing with linear probing tends to be faster than chaining (linking elements with linked lists)?
  5. Sorting methods with a fixed sequence of compare-exchange steps (sorting networks), such as bitonic sort, are sometimes used for sorting on parallel hardware such as GPUs. Why?