Loading...

Preview

Showing 4 of 11 steps

Login to see all

Coin Change (Greedy)

Easy

Coin Change (Greedy)

Make change with minimum coins using largest first

📊 Complexity

Type	Value
Best	O(n)
Average	O(n)
Worst	O(n)
Space	O(1)

🏷️ Tags

GreedyCoinsDivision

📖 Introduction

Greedy coin change uses the largest coins first. It guarantees optimal solution when coins are multiples of each other (e.g., 500, 100, 50, 10).

1/11

Loading...

💰Coin Change Problem

Need to give 1260 won as change. Use minimum number of coins!

Basics

Coin Change (Greedy)

Definition

Greedy coin change uses the largest coins first. It guarantees optimal solution when coins are multiples of each other (e.g., 500, 100, 50, 10).

Key Characteristics

✓Key: Use largest coins as much as possible
✓Calculation: Use quotient and remainder
✓Condition: Optimal only when coins are multiples
✓Counter: [1,3,4] for 6 → greedy(4+1+1=3) vs optimal(3+3=2)

Time Complexity

Best

O(n)

Average

O(n)

Worst

O(n)

Space Complexity

O(1)

Coin Change (Greedy) | AlgoNote