The ultimate guide to coding interviews. Developed by FAANG engineers. Boost problem-solving skills with number theory, dynamic programming, and graph theory. Get interview-ready in just a few hours.

Competitive Programming - Crack Your Coding Interview.png

Whether you’re gearing up for online coding challenges, code-a-thons, or interviews, then this course is for you. With this course, you will solidify your problem-solving skills ensuring a swift sail through any problem. 


You will be tasked with solving some of the most frequently asked questions that are brought up in FAANG interviews. You will start with the concepts of Number Theory and Divide and Conquer, and gradually move towards more complex problems like dynamic programming and graph theory.


With each problem you solve, there will be insightful explanations and full implementation details to really hammer home the concepts. By the time you finish this course, you will have the confidence to solve any problem, no matter the difficulty.

Competitive Programming - Crack Your Coding Interview, C++

## Problem statement
**If we have an infinite supply of each of C = {  $C_{1}$,  $C_{2}$, ... , $C_{M}$} valued coins and we want to make a change for a given value (N) of cents, what is the minimum number of coins required to make the change?**

```m
Example ->
Input: 
coins[] = {25, 10, 5}, N = 30
Output: Minimum 2 coins required
We can use one coin of 25 cents and one of 5 cents.
Input: 
coins[] = {9, 6, 5, 1}, N = 13
Output: Minimum 3 coins required
We can use one coin of 6 + 6 + 1 cents coins.
```

## Solution: `Recursive approach`

Start the solution with $sum = N$ cents and in each iteration, find the minimum coins required by dividing the problem into subproblems where we take a coin from {$C_{1}$, $C_{2}$, ..., $C_{M}$} and decrease the sum, $N$,
by $C[i]$ (depending on the coin we took). Whenever $N$ becomes 0, we have a possible
solution. To find the optimal answer, we return the minimum of all answers for which $N$ became 0.

Let's discuss the recurrence relation now.
* **Base case**: If `N == 0`, then 0 coins are required.
* **Recursive case**: If `N > 0` then, the recurrence relation for this problem can be

   **minCoins(N , coins[0..m-1]) = min {1 + minCoins(N-coin[i], coins[0....m-1])}**,
where `i` varies from `0` to `m-1` and `coin[i] <= N`.

Let's move on to the implementation now.

# Problem statement
**If we have an infinite supply of each of C = {  $C_{1}$,  $C_{2}$, ... , $C_{M}$} valued coins and we want to make a change for a given value (N) of cents, what is the minimum number of coins required to make the change?**

```m
Example ->
Input: 
coins[] = {25, 10, 5}, N = 30
Output: Minimum 2 coins required
We can use one coin of 25 cents and one of 5 cents.
Input: 
coins[] = {9, 6, 5, 1}, N = 13
Output: Minimum 3 coins required
We can use one coin of 6 + 6 + 1 cents coins.
```

# Solution: `Recursive approach`

Start the solution with $sum = N$ cents and in each iteration, find the minimum coins required by dividing the problem into subproblems where we take a coin from {$C_{1}$, $C_{2}$, ..., $C_{M}$} and decrease the sum, $N$,
by $C[i]$ (depending on the coin we took). Whenever $N$ becomes 0, we have a possible
solution. To find the optimal answer, we return the minimum of all answers for which $N$ became 0.

Let's discuss the recurrence relation now.
* **Base case**: If `N == 0`, then 0 coins are required.
* **Recursive case**: If `N > 0` then, the recurrence relation for this problem can be

   **minCoins(N , coins[0..m-1]) = min {1 + minCoins(N-coin[i], coins[0....m-1])}**,
where `i` varies from `0` to `m-1` and `coin[i] <= N`.

Let's move on to the implementation now.

Understand the problem and build a brute force solution.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Minimum Coin Change Problem

Problem statement