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 introduction
The Chinese Remainder theorem is used to solve problems typical of the form "*Find a number which when divided by 2 leaves remainder 1, when divided by 3 leaves remainder 2, and when divided by 7 leaves remainder 5*". These problems can be reformulated into a system of linear congruence and can then be solved using the Chinese Remainder theorem.
For example, the above problem can be expressed as a system of three linear congruences:
```
x ≡ 1 (mod 2), x ≡ 2 mod(3), x ≡ 5 mod (7)
```
We are given with two arrays, i.e., `num[]` and `rem[]`. For the above example, we can have `num[] = {2, 3, 7}` and `rem[] = {1, 2, 5}`.
The Chinese Remainder theorem states that there always exists an x that satisfies given congruence.
Basically, we are given `k` numbers which are pairwise co-prime and given remainders of these numbers when an unknown number `x` is divided by them. We need to find the minimum possible value of `x` that produces given remainders. In other words, we can say that there exists a value of `x` for the below relations:
```
x % num[0] = rem[0],
x % num[1] = rem[1],
.......................
x % num[k-1] = rem[k-1]
```
# Solution

A naive approach is to find `x` is to start with `1` and one by one increment it and check if it is divisible with given elements in `num[]` and if it produces corresponding remainders in `rem[]`. Once we find such an `x`, we get our solution.

But obviously, the naive approach would have a large time complexity if the numbers are more. So, according to the Chinese Remainder theorem 

> **x** = $\sum_{0<=i<=(n-1)}^n$ (*rem[i]* * *pp[i]* * *inv[i]*)) % *prod* 

where 
* **rem[i]** is the given array of remainders
* **prod** is the product of all given numbers
* **prod** = `num[0] * num[1] * ... * num[k-1]`
* **pp[i]** is product of all except for num[i]
* **pp[i]** = `prod / num[i]`
* **inv[i]** = Modular Multiplicative Inverse of `pp[i]` with respect to `num[i]`

Learn about the Chinese Remainder theorem that is very useful in solving coding interview problems.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Chinese Remainder Theorem

Problem introduction