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


***On a positive integer, you can perform any one of the following 3 steps:***

***1. Subtract 1 from it.***

***2. If it is divisible by 2, divide by 2.***

***3. If it is divisible by 3, divide by 3.*** 

***Given a positive integer n, find the minimum number of steps that takes n to 1.***

Wait a second!! You might be thinking that this is a pretty simple problem. One can think of greedily choosing the step that makes `n` as low as possible and continues the same till it reaches  1. If you observe carefully, the greedy strategy doesn't work here. 

Let us take `n` = 10. If we use the  Greedy approach, we get the following steps:

* Step 1: `10 / 2 = 5`
* Step 2: `5 - 1 = 4` 
* Step 3: `4 / 2 = 2` 
* Step 4: `2 / 2 = 1`

So the total number of steps required is **4**. But the optimal way is this:
* Step 1: `10 - 1 = 9` 
* Step 2: `9 / 3 = 3`
* Step 3: `3 / 3 = 1`

Hence, the total number of steps must be **3**. We need to try out all possible steps that we can make for each possible value of n that we encounter and choose the minimum of these possibilities.

Thus, this is not a Greedy problem. 

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 Steps to One Problem

Problem statement