Coding To 1Cr ~ Nitesh Synergy

Pease check git repo code & research 1Cr Problem Statements & Solutions

https://github.com/niteshsynergy/DSA_Phase1

https://github.com/niteshsynergy/DSA_Phase2

https://github.com/niteshsynergy/DSA_Phase3

https://github.com/niteshsynergy/Code1CrPlusMission

https://github.com/niteshsynergy/ResearchProblemsCoding1CrPlus

https://github.com/niteshsynergy/techassign/

DSA To 1Cr Coding~ Notes Available ~ Offline + Github

DSA Weekly Syllabus :

Phase 1: Introduction

phase 2: DSA Topic Code Practice: https://github.com/niteshsynergy/DSA_Phase2

WeekTopic - Phase 2 pratice code for each topic curd operations So that become expert of each topic
Week 1Introduction to DSA + Time & Space Complexity & Arrays (Basics, Sliding Window, Prefix Sum) & Strings (Palindrome, Anagram, Substring Search)
Week 2Searching Algorithms (Linear, Binary Search & Variants) 
Week 3 Sorting Algorithms (Bubble, Merge, Quick, Count Sort)
Week 4Hashing (HashMap, HashSet, Frequency Maps, Hashing Tricks)
Week 5Stack (NGE, Stock Span, Balanced Brackets, Histogram Area)
Week 6Queue & Deque (Circular Queue, Sliding Window Maximum)
Week 7Linked List (Reverse, Detect Loop, Merge, K-Reverse)
Week 8Trees - Part 1 (Traversals, Height, Diameter, Leaf Count) & Trees - Part 2 (Binary Search Tree, LCA, Floor/Ceil, Insertion/Deletion)
Week 9Heaps & Priority Queue (Heap Sort, Kth Largest, Median in Stream)
Week 10Tries (Prefix Matching, Auto-complete, Word Dictionary)
Week 11Graphs - Part 1 (BFS, DFS, Connected Components, Grid Problems) & Graphs - Part 2 (Dijkstra, Kruskal, Prim’s, Topological Sort, Cycle Detection)
Week 12Recursion + Backtracking (N-Queens, Subsets, Maze)
Week 13Dynamic Programming - Part 1 (Fibonacci, 0/1 Knapsack, LCS, LIS)
Week 14Dynamic Programming - Part 2 (Matrix Chain Multiplication, Partition, Palindromes)
Week 15Greedy Algorithms (Activity Selection, Job Sequencing, Interval Problems)
Week 16Sliding Window + Two Pointers (Max Sum Subarray, Rainwater, Unique Window)
Week 17Bit Manipulation (XOR, Bit Masks, Single Number, Count Set Bits)
Week 18Segment Tree & Disjoint Set Union (Range Queries, Union-Find)
 

Week	Topic - Phase 2 pratice code for each topic curd operations So that become expert of each topic
Week 1	Introduction to DSA + Time & Space Complexity & Arrays (Basics, Sliding Window, Prefix Sum) & Strings (Palindrome, Anagram, Substring Search)
Week 2	Searching Algorithms (Linear, Binary Search & Variants)
Week 3	Sorting Algorithms (Bubble, Merge, Quick, Count Sort)
Week 4	Hashing (HashMap, HashSet, Frequency Maps, Hashing Tricks)
Week 5	Stack (NGE, Stock Span, Balanced Brackets, Histogram Area)
Week 6	Queue & Deque (Circular Queue, Sliding Window Maximum)
Week 7	Linked List (Reverse, Detect Loop, Merge, K-Reverse)
Week 8	Trees - Part 1 (Traversals, Height, Diameter, Leaf Count) & Trees - Part 2 (Binary Search Tree, LCA, Floor/Ceil, Insertion/Deletion)
Week 9	Heaps & Priority Queue (Heap Sort, Kth Largest, Median in Stream)
Week 10	Tries (Prefix Matching, Auto-complete, Word Dictionary)
Week 11	Graphs - Part 1 (BFS, DFS, Connected Components, Grid Problems) & Graphs - Part 2 (Dijkstra, Kruskal, Prim’s, Topological Sort, Cycle Detection)
Week 12	Recursion + Backtracking (N-Queens, Subsets, Maze)
Week 13	Dynamic Programming - Part 1 (Fibonacci, 0/1 Knapsack, LCS, LIS)
Week 14	Dynamic Programming - Part 2 (Matrix Chain Multiplication, Partition, Palindromes)
Week 15	Greedy Algorithms (Activity Selection, Job Sequencing, Interval Problems)
Week 16	Sliding Window + Two Pointers (Max Sum Subarray, Rainwater, Unique Window)
Week 17	Bit Manipulation (XOR, Bit Masks, Single Number, Count Set Bits)
Week 18	Segment Tree & Disjoint Set Union (Range Queries, Union-Find)

What is DSA (Data Structures and Algorithms)?

DSA stands for Data Structures and Algorithms. It is the core foundation of computer science that helps in writing efficient and optimized code.

Why DSA is Needed

Reason	Explanation
Efficient Code	Helps you write faster, memory-optimized code.
Problem Solving	Sharpens your logical thinking and structured approach.
Interview Preparation	Almost every tech company focuses on DSA in coding interviews (Amazon, Google, etc.).
Build Strong Foundations	Boosts confidence to learn advanced topics like AI, OS, Networks.
Competitive Programming	DSA is the core of platforms like LeetCode, Codeforces, HackerRank.
System Design Help	Understanding how data is structured gives a deep insight into system architecture.

Types of Data Structures (DS)

1. Linear Data Structures

Data is organized in a sequential (linear) manner.

Type	Description	Example Use Case
Array	Collection of elements stored at contiguous memory	Storing list of items
Linked List	Elements are connected via pointers	Dynamic memory allocation
Stack	LIFO (Last In, First Out)	Undo operations
Queue	FIFO (First In, First Out)	Scheduling processes
Deque	Double-ended queue	Browser history, palindromes

2. Non-Linear Data Structures

Data is organized hierarchically or in complex relationships.

Type	Description	Example Use Case
Tree	Hierarchical structure	File systems, HTML DOM
Binary Tree / BST	Binary tree with ordering	Searching, sorting
Heap (Min/Max)	Complete binary tree for priority	Priority queue
Trie	Prefix tree	Autocomplete, dictionary
Graph	Nodes connected by edges	Maps, social networks

3. Hash-Based Structures

Efficient access using hash functions.

Type	Description	Example Use Case
Hash Table / HashMap	Key-value pairs	Caching, fast lookups
HashSet	Unique elements only	Duplicate detection

Types of Algorithms (A)

1. Searching Algorithms

Used to find a specific element in a structure.

Type	Description
Linear Search	Check each element one-by-one
Binary Search	Search in sorted data (divide & conquer)

2. Sorting Algorithms

Used to reorder elements.

Type	Description
Bubble Sort	Compare adjacent elements
Selection Sort	Select min/max and place
Insertion Sort	Build sorted list
Merge Sort	Divide and conquer
Quick Sort	Partition-based divide & conquer
Heap Sort	Use heap data structure

3. Recursion & Backtracking

Call function within itself and explore all possibilities.

Type	Description
Recursion	Solve via repeated calls
Backtracking	Try all solutions and backtrack if needed (used in puzzles, path finding)

4. Dynamic Programming (DP)

Break down problems into subproblems and store their results (memoization/tabulation).

Use Case	Examples
DP	Fibonacci, Knapsack, Longest Common Subsequence (LCS)

5. Greedy Algorithms

Make the locally optimal choice at each step.

Use Case	Examples
Greedy	Coin change, Activity selection, Huffman coding

6. Divide and Conquer

Divide the problem into subproblems, solve them independently, then combine.

Use Case	Examples
Divide & Conquer	Merge sort, Quick sort, Binary search

7. Graph Algorithms

Used for graph-related problems.

Type	Description
DFS / BFS	Explore graphs
Dijkstra’s	Shortest path
Kruskal’s / Prim’s	Minimum spanning tree
Topological Sort	Task scheduling

→ Next →

Lets start from basic→

1. Time and Space Complexity

What is Time Complexity?

Time Complexity measures the amount of computational time an algorithm takes relative to the input size n.

Think of it as:

"How does the algorithm scale as input grows?"

It’s about how many operations your code performs, not about how long in seconds it takes (that depends on hardware).

What is Space Complexity?

Space Complexity refers to the amount of memory an algorithm uses relative to the input size. This includes:

Input space
Auxiliary space (temporary data structures, recursion stack, etc.)

Part 1: Big-O, Big-Theta, Big-Omega

These are formal notations that describe growth rates:

Notation	Represents	Meaning
O(f(n))	Big-O	Upper bound (Worst-case scenario)
Ω(f(n))	Big-Omega	Lower bound (Best-case scenario)
Θ(f(n))	Big-Theta	Tight bound (When upper = lower = actual)

Big-O (O) – Worst-case

"The algorithm won't be worse than this."

Example:

int findMax(int[] arr) {
   int max = arr[0];
   for (int i = 1; i < arr.length; i++) {
       if (arr[i] > max) max = arr[i];
   }
   return max;
}

Time Complexity: O(n) – because in the worst case, we scan all elements.

Use Big-O in interviews because companies want to know how bad your solution can get.

Big-Omega (Ω) – Best-case

"The algorithm won't be better than this."

Same example:

if (arr.length == 1) return arr[0];

Best case: Ω(1) – if array size is 1.

Big-Theta (Θ) – Tight bound

"It always behaves like this."

When the algorithm runs exactly in linear time, regardless of input (no best or worst):

for (int i = 0; i < n; i++) System.out.println(i);

Time: Θ(n)

Part 2: Best, Average, Worst Case

Why Case Analysis Matters:

Best case = Impractical optimism
Average case = Real-world expectation
Worst case = Safety net

Example: Linear Search

int find(int[] arr, int key) {
   for (int i = 0; i < arr.length; i++) {
       if (arr[i] == key) return i;
   }
   return -1;
}

Case	Scenario	Time Complexity

Best Case Key is at arr[0] O(1)

Worst Case Key is at arr[n-1] or not found O(n)

Average Case Key is somewhere in the middle O(n)

Part 3: Common Time Complexities (With Examples)

Complexity	Description	Example
`O(1)`	Constant Time	Accessing an array element
`O(log n)`	Logarithmic	Binary Search
`O(n)`	Linear	Loop through array
`O(n log n)`	Linearithmic	Merge Sort, Quick Sort (avg)
`O(n²)`	Quadratic	Nested loops (Bubble Sort)
`O(2ⁿ)`	Exponential	Recursion (Fibonacci without DP)
`O(n!)`	Factorial	Generating all permutations

For anything above O(n log n), optimize it unless the input size is guaranteed small.

Part 4: Space vs Time Trade-offs

Often, you trade more memory to get faster time, or vice versa.

Example: Caching / Memoization

Map<Integer, Integer> cache = new HashMap<>();

int fib(int n) {
   if (cache.containsKey(n)) return cache.get(n);
   if (n <= 1) return n;
   int result = fib(n - 1) + fib(n - 2);
   cache.put(n, result);
   return result;
}

Without Memoization	`O(2ⁿ)` Time, `O(n)` Space

With Memoization O(n) Time, O(n) Space

Space used = performance gained

Real-Life Examples

Use Case	Time Complexity	Why It Matters
Searching in DB Index	`O(log n)`	Fast access, scalable
Google Search Ranking	`O(n log n)`	Efficient sorting & relevance
Encryption (RSA)	`O(log n)` or more	Needs prime checking
AI Neural Net Training	`O(n^2)`+	Huge memory and CPU needed
Image Compression	`O(n)`	Balance quality vs. processing time

2. Mathematics for DSA

Prime Numbers — Sieve of Eratosthenes (In-Depth)

What is a Prime Number?

A prime number is a natural number greater than 1 that has exactly two divisors: 1 and itself.
Examples: 2, 3, 5, 7, 11, 13, 17, ...

Non-prime numbers are called composite numbers (like 4, 6, 8, 9, etc.).

Why Are Prime Numbers Important in DSA?

Used in Hash Functions to reduce collisions.
Core to modular arithmetic & cryptography (RSA, Diffie-Hellman).
Appear in probability, factorization, LCM/GCD, sieve optimizations.
Used in primality testing, number theory, counting divisors, and modular inverses.

Brute Force Approach: Primality Check

Check if a number n is divisible by any number from 2 to sqrt(n).

boolean isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) return false;
}
return true;
}

Time Complexity: `O(√n)`

Not feasible for finding primes up to 10^6 or 10^7.
Hence, we need an optimized algorithm...

Sieve of Eratosthenes

Purpose:

To find all prime numbers up to a given number N in O(n log log n) time.

Core Idea:

If a number is not prime, it must be divisible by some smaller prime number.
So, we:

Assume all numbers from 2 to N are prime.
Start from 2, mark its multiples as not prime.
Move to next unmarked number and repeat.

Steps:

Let’s say N = 30
We'll maintain a boolean array isPrime[0…30], initialized to true (except isPrime[0] = false, isPrime[1] = false)

boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
   if (isPrime[i]) {
       for (int j = i * i; j <= n; j += i) {
           isPrime[j] = false;
       }
   }
}

Time Complexity Analysis:

Outer loop runs for √n iterations.
Inner loop marks multiples of primes.
→ Number of operations:
n/2 + n/3 + n/5 + n/7 + ... ≈ n * log(log n)

So, Total Time: O(n log log n)

Space Complexity:

O(n) for the isPrime[] boolean array.

Visual Walkthrough: `N = 30`

Initial Array (T = True):

[ F, F, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T ]
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

→ Start with i = 2 → mark 4, 6, 8, 10...30

Next i = 3 → mark 9, 12, 15, 18...30

Skip 4 (already false), next i = 5, mark 25, 30...

Final isPrime[] shows all prime indices:

[ F, F, T, T, F, T, F, T, F, F, F, T, F, T, F, F, F, T, F, T, F, F, F, T, F, F, F, T, F, T, F ]
→ Indices that are still true: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Optimizations

Sieve from `i * i` instead of `2*i`

Start marking multiples from i * i because smaller multiples are already handled.

Segmented Sieve

Used when N is large (e.g. 10^9), and memory is limited.
It divides the range into chunks and applies the sieve in segments.Applications of Sieve

Use Case	Description
Cryptography	RSA uses large primes for public/private key generation
Competitive Programming	Problems involving factorization, coprime pairs, LCM/GCD
Totient Function	`φ(n)` uses prime factorization
Number Theory	Sum/count of divisors, Euler’s Theorem
Preprocessing Primes	For quick lookups in coding interviews

What is GCD & LCM?

GCD (Greatest Common Divisor): Largest number that divides two numbers without a remainder.
LCM (Least Common Multiple): Smallest number divisible by both numbers.

Euclidean Algorithm for GCD

Key idea:
gcd(a, b) = gcd(b, a % b) and gcd(a, 0) = a.

Code: GCD (Iterative & Recursive)

// Recursive GCD
int gcd(int a, int b) {
   if (b == 0) return a;
   return gcd(b, a % b);
}
// Iterative GCD
int gcdIter(int a, int b) {
   while (b != 0) {
       int temp = b;
       b = a % b;
       a = temp;
   }
   return a;
}

Problem: Find GCD of two numbers

Example:
Find GCD of a = 48 and b = 18.

int gcd(int a, int b) {
if (b == 0) return a; // Base case: if second number is 0, gcd is 'a'
return gcd(b, a % b); // Recursive call with (b, remainder of a divided by b)
}

How it works for gcd(48, 18):

Step 1: gcd(48, 18)
- b != 0, so call gcd(18, 48 % 18) → gcd(18, 12)
Step 2: gcd(18, 12)
- b != 0, so call gcd(12, 18 % 12) → gcd(12, 6)
Step 3: gcd(12, 6)
- b != 0, so call gcd(6, 12 % 6) → gcd(6, 0)
Step 4: gcd(6, 0)
- b == 0, so return a → return 6

Now the recursive calls unwind, and final result is 6.

2. Iterative GCD

int gcdIter(int a, int b) {
while (b != 0) {
int temp = b; // Store current b
b = a % b; // Update b to remainder of a divided by b
a = temp; // Update a to old b value
}
return a; // When b is 0, a is the GCD
}

How it works for gcdIter(48, 18):

Initial values: a=48, b=18
Loop 1:
- temp = 18
- b = 48 % 18 = 12
- a = 18
Now a=18, b=12
Loop 2:
- temp = 12
- b = 18 % 12 = 6
- a = 12
Now a=12, b=6
Loop 3:
- temp = 6
- b = 12 % 6 = 0
- a = 6
Now a=6, b=0 → exit loop

Return a = 6

LCM Using GCD

Formula:

$LCM(a,b)=∣a×b∣GCD(a,b)LCM(a, b) = \frac{|a \times b|}{GCD(a, b)}$

$LCM$ $($ $a$ $,$ $b$ $)$ $=$ $GCD$ $($ $a$ $,$ $b$ $)$ $∣$ $a$ $\times$ $b$ $∣$ $$

Code:

int lcm(int a, int b) {
return (a / gcd(a, b)) * b;
}

Example: Calculate LCM(48, 18)

Step 1: Find gcd(48, 18)

From previous example, gcd(48, 18) = 6

Step 2: Calculate LCM

LCM = (48 / 6) * 18
LCM = 8 * 18 = 144
Verification:
48 divides 144 (144 / 48 = 3)
18 divides 144 (144 / 18 = 8)
There is no smaller positive number divisible by both 48 and 18 than 144.
So, LCM(48, 18) = 144 is correct.

Why Important?
Used in fractions simplification.
Helps in synchronizing cycles, periodicity problems.
Core in problems related to number theory and modular arithmetic.

Modular Arithmetic

What?

Performing arithmetic operations under a modulus (usually a prime number or large number like 10^9+7).
E.g., compute (a + b) % mod, (a * b) % mod.

Why?

To avoid integer overflow.
Used heavily in cryptography, hashing, combinatorics.
Keeps numbers in manageable range.

Common Operations

Addition: (a + b) % mod
Subtraction: (a - b + mod) % mod (to avoid negatives)
Multiplication: (a * b) % mod
Division: Use modular inverse (if mod is prime, use Fermat’s Little Theorem)

long mod = 1_000_000_007;
long modAdd(long a, long b) {
   return (a + b) % mod;
}
long modMul(long a, long b) {
   return (a * b) % mod;
}

Power Exponentiation (Fast Power)

Problem:

Calculate $abmod ma^b \mod m$ $a$ $b$ $mod$ $m$ efficiently for large $b$ .

Naive:

Multiply $a$ by itself $b$ times → O(b) time, too slow for large b.

Fast Exponentiation:

Use divide and conquer by exploiting:

$ab={(ab/2)2b evena×ab−1b odda^b = \begin{cases} (a^{b/2})^2 & b \text{ even} \\ a \times a^{b-1} & b \text{ odd} \end{cases}$

$a$ $b$ $=$ ${$ $($ $a$ $b$ $/2$ $)$ $2$ $a$ $\times$ $a$ $b$ $-$ $1$ $$ $b$ $even$ $b$ $odd$ $$

Code (Recursive):

long modPow(long a, long b, long mod) {
   if (b == 0) return 1;
   long half = modPow(a, b / 2, mod);
   long result = (half * half) % mod;
   if (b % 2 == 1) result = (result * a) % mod;
   return result;
}

Example: Calculate $313mod 173^{13} \mod 17$ $3$ $13$ $mod$ $17$

We want:
$313mod 173^{13} \mod 17$ $3$ $13$ $mod$ $17$

Step-by-step trace:

Call: modPow(3, 13, 17)

Since b=13 ≠ 0, recursive call with b/2 = 6:

Call: modPow(3, 6, 17)

Since b=6 ≠ 0, recursive call with b/2 = 3:

Call: modPow(3, 3, 17)

Since b=3 ≠ 0, recursive call with b/2 = 1:

Call: modPow(3, 1, 17)

Since b=1 ≠ 0, recursive call with b/2 = 0:

Call: modPow(3, 0, 17)

b=0 → return 1

Returning back:

From modPow(3,0,17): returns 1
modPow(3,1,17):
- half = 1
- result = (1 * 1) % 17 = 1
- b is odd (1 % 2 == 1), so result = (1 * 3) % 17 = 3
- returns 3
modPow(3,3,17):
- half = modPow(3,1,17) = 3
- result = (3 * 3) % 17 = 9
- b is odd (3 % 2 == 1), so result = (9 * 3) % 17 = 27 % 17 = 10
- returns 10
modPow(3,6,17):
- half = modPow(3,3,17) = 10
- result = (10 * 10) % 17 = 100 % 17 = 15
- b is even (6 % 2 == 0), no extra multiplication
- returns 15
modPow(3,13,17):
- half = modPow(3,6,17) = 15
- result = (15 * 15) % 17 = 225 % 17 = 4
- b is odd (13 % 2 == 1), so result = (4 * 3) % 17 = 12
- returns 12

Final result:

$313mod 17=123^{13} \mod 17 = 12$

$3$ $13$ $mod$ $17$ $=$ $12$

Time Complexity:

O(log b) — drastically faster than naive.

Combinatorics (nCr, nPr)

Definitions:

nCr: Number of ways to choose r items from n without order.
nPr: Number of ways to arrange r items from n (order matters).

Formulas:

$nCr=n!r!(n−r)!nCr = \frac{n!}{r! (n-r)!}$

$nCr$ $=$ $r$ $!$ $($ $n$ $-$ $r$ $)!$ $n$ $!$ $$

Efficient Calculation with Modulus:

Precompute factorials and inverse factorials to calculate $nCr$ modulo $mod$ .

Code (Precompute factorials):

long mod = 1_000_000_007;
int MAX = 1000000;
long[] fact = new long[MAX+1];
long[] invFact = new long[MAX+1];

void precompute() {
fact[0] = 1;
for (int i = 1; i <= MAX; i++) {
fact[i] = (fact[i-1] * i) % mod;
}
invFact[MAX] = modInverse(fact[MAX], mod);
for (int i = MAX-1; i >= 0; i--) {
invFact[i] = (invFact[i+1] * (i+1)) % mod;
}
}

// Modular inverse using Fermat's little theorem (mod must be prime)
long modInverse(long a, long m) {
return modPow(a, m - 2, m);
}

long nCr(int n, int r) {
if (r > n) return 0;
return (((fact[n] * invFact[r]) % mod) * invFact[n - r]) % mod;
}

Step 1: Precompute factorials fact[]

fact[0] = 1;
for (int i = 1; i <= MAX; i++) {
fact[i] = (fact[i-1] * i) % mod;
}

fact[i] stores $i$ $!$ mod mod.
For example:
- fact[1] = 1! = 1
- fact[2] = 2! = 2
- fact[3] = 6
- fact[4] = 24, etc., all modulo mod.

Step 2: Precompute inverse factorials invFact[]

invFact[MAX] = modInverse(fact[MAX], mod);
for (int i = MAX-1; i >= 0; i--) {
invFact[i] = (invFact[i+1] * (i+1)) % mod;
}

invFact[i] stores modular inverse of fact[i], i.e., $(i!)−1mod mod(i!)^{-1} \mod mod$ $($ $i$ $!)$ $-1$ $mod$ $mod$ .
Start from invFact[MAX] using modular inverse of fact[MAX].
Then compute inverses going backward using:

$invFact[i]=invFact[i+1]×(i+1)mod modinvFact[i] = invFact[i+1] \times (i+1) \mod mod$

$invFact$ $[$ $i$ $]$ $=$ $invFact$ $[$ $i$ $+$ $1$ $]$ $\times$ $($ $i$ $+$ $1$ $)$ $mod$ $mod$

This works because:

$(i!)−1=((i+1)!)−1×(i+1)mod mod(i!)^{-1} = ((i+1)!)^{-1} \times (i+1) \mod mod$

$($ $i$ $!)$ $-1$ $=$ $(($ $i$ $+$ $1$ $)!)$ $-1$ $\times$ $($ $i$ $+$ $1$ $)$ $mod$ $mod$

$Step 3: Modular inverse function (Fermat’s Little Theorem)$

$long modInverse(long a, long m) {$
$return modPow(a, m - 2, m);$
$}$

Uses Fermat’s little theorem:
If m is prime, inverse of a modulo m is:
$am−2mod ma^{m-2} \mod m$ $a$ $m$ $-$ $2$ $mod$ $m$
Uses your previously defined modPow for fast exponentiation.

Step 4: Calculate nCr modulo mod

long nCr(int n, int r) {
if (r > n) return 0;
return (((fact[n] * invFact[r]) % mod) * invFact[n - r]) % mod;
}

Formula for binomial coefficient modulo prime:

$(nr)=n!r!(n−r)!mod mod=fact[n]×invFact[r]×invFact[n−r]mod mod\binom{n}{r} = \frac{n!}{r! (n-r)!} \mod mod = fact[n] \times invFact[r] \times invFact[n-r] \mod mod$

$($ $rn$ $$ $)$ $=$ $r$ $!$ $($ $n$ $-$ $r$ $)!$ $n$ $!$ $$ $mod$ $mod$ $=$ $fact$ $[$ $n$ $]$ $\times$ $invFact$ $[$ $r$ $]$ $\times$ $invFact$ $[$ $n$ $-$ $r$ $]$ $mod$ $mod$

Example: Calculate $(52)mod 1,000,000,007\binom{5}{2} \mod 1,000,000,007$ $($ $25$ $$ $)$ $mod$ $1$ $,$ $000$ $,$ $000$ $,$ $007$

fact[5] = 120
invFact[2] = modular inverse of 2! = modular inverse of 2 = 500000004
invFact[3] = modular inverse of 3! = modular inverse of 6 = 166666668

Calculate:

$nCr=(120×500000004×166666668)mod 1,000,000,007nCr = (120 \times 500000004 \times 166666668) \mod 1,000,000,007$

$nCr$ $=$ $($ $120$ $\times$ $500000004$ $\times$ $166666668$ $)$ $mod$ $1$ $,$ $000$ $,$ $000$ $,$ $007$

Stepwise:

$120×500000004≡60mod 1,000,000,007120 \times 500000004 \equiv 60 \mod 1,000,000,007$ $120$ $\times$ $500000004$ $\equiv$ $60$ $mod$ $1$ $,$ $000$ $,$ $000$ $,$ $007$
$60×166666668≡10mod 1,000,000,00760 \times 166666668 \equiv 10 \mod 1,000,000,007$ $60$ $\times$ $166666668$ $\equiv$ $10$ $mod$ $1$ $,$ $000$ $,$ $000$ $,$ $007$

So, $(52)=10\binom{5}{2} = 10$ $($ $25$ $$ $)$ $=$ $10$ , which is correct.

Why precompute?

Factorials and inverse factorials are expensive to compute repeatedly.
Precomputing lets you calculate any nCr quickly in O(1) time after O(MAX) preprocessing.

Prefix Sum & Difference Arrays

Prefix Sum:

Precompute sums to answer sum queries efficiently.

Example:

Given array arr = [1, 2, 3, 4]
Prefix sum prefix = [0, 1, 3, 6, 10] (0-based for ease)
Sum from l to r:

sum = prefix [ r + 1 ] − prefix [ l ]

Code:

int[] prefixSum(int[] arr) {
int n = arr.length;
int[] prefix = new int[n + 1];
prefix[0] = 0;
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i-1] + arr[i-1];
}
return prefix;
}

// Query sum l to r
int rangeSum(int[] prefix, int l, int r) {
return prefix[r+1] - prefix[l];
}

Step by step:

arr = [ 2 , 4 , 5 , 7 , 8 ]

Step 1: Compute prefix sums

prefix[0] = 0 (by definition)
prefix[1] = prefix[0] + arr[0] = 0 + 2 = 2
prefix[2] = prefix[1] + arr[1] = 2 + 4 = 6
prefix[3] = prefix[2] + arr[2] = 6 + 5 = 11
prefix[4] = prefix[3] + arr[3] = 11 + 7 = 18
prefix[5] = prefix[4] + arr[4] = 18 + 8 = 26

So, prefix array is:

prefix = [0, 2, 6, 11, 18, 26]

Step 2: Query sums using `rangeSum`

Query: sum of elements from index l=1 to r=3 (which means elements 4, 5, 7)

Calculate:

rangeSum(prefix, 1, 3) = prefix[3 + 1] - prefix[1] = prefix[4] - prefix[1] = 18 - 2 = 16

Check manually:

arr[1] + arr[2] + arr[3] = 4 + 5 + 7 = 16

Perfect!

Difference Array:

For efficient range update queries.

Idea:

To add val to range [l, r] in O(1):

diff[l] += val
diff[r+1] -= val (if r+1 < n)

Then prefix sum of diff gives the updated array.

Code:

int[] buildDiffArray(int[] arr) {
int n = arr.length;
int[] diff = new int[n];
diff[0] = arr[0];
for (int i = 1; i < n; i++) {
diff[i] = arr[i] - arr[i-1];
}
return diff;
}

void rangeUpdate(int[] diff, int l, int r, int val) {
diff[l] += val;
if (r + 1 < diff.length) diff[r+1] -= val;
}

int[] buildUpdatedArray(int[] diff) {
int n = diff.length;
int[] arr = new int[n];
arr[0] = diff[0];
for (int i = 1; i < n; i++) {
arr[i] = arr[i-1] + diff[i];
}
return arr;
}

Explanation with example:

Suppose:arr = [10, 20, 30, 40, 50]
Step 1: Build difference array

diff[0] = arr[0] = 10
diff[1] = arr[1] - arr[0] = 20 - 10 = 10
diff[2] = 30 - 20 = 10
diff[3] = 40 - 30 = 10
diff[4] = 50 - 40 = 10

So,

diff = [10, 10, 10, 10, 10]
Step 2: Range update

Now suppose you want to add 5 to elements from index 1 to 3 (i.e., arr[1], arr[2], arr[3])

Call:

rangeUpdate(diff, 1, 3, 5);

Effect on diff:

diff[1] += 5 → diff[1] = 10 + 5 = 15
diff[4] -= 5 → diff[4] = 10 - 5 = 5 (because 3+1 = 4)

Updated diff:

diff = [10, 15, 10, 10, 5]

Step 3: Rebuild updated array

Rebuild with prefix sums of diff:

arr[0] = diff[0] = 10
arr[1] = arr[0] + diff[1] = 10 + 15 = 25
arr[2] = arr[1] + diff[2] = 25 + 10 = 35
arr[3] = arr[2] + diff[3] = 35 + 10 = 45
arr[4] = arr[3] + diff[4] = 45 + 5 = 50

Resulting updated array:

[10, 25, 35, 45, 50]

Check update:

Original array was [10, 20, 30, 40, 50]
After adding 5 to indices 1 to 3:

arr[1] = 20 + 5 = 25
arr[2] = 30 + 5 = 35
arr[3] = 40 + 5 = 45

All other elements unchanged. Perfect!

Why use difference array?

Normally, updating values in a range [l, r] by adding val takes O(r-l+1) time if done naively.
Using difference array, each range update is done in O(1) time by updating only two positions.
Rebuilding the final array after all updates takes O(n) time.

Bit Manipulation

Why Bit Manipulation?

Fast operations at the bit level.
Useful in problems with flags, subsets, masks, parity, counting bits, etc.
Operates in constant time on integers.

Common Operations:

Operation	Symbol	Description
AND	&	Bitwise AND
OR	\|	Bitwise OR
XOR	^	Bitwise XOR
NOT	~	Bitwise NOT
Left Shift	<<	Shift bits left (multiply by 2)
Right Shift	>>	Shift bits right (divide by 2)

Examples:

Check if ith bit is set

boolean isSet(int n, int i) {
return (n & (1 << i)) != 0;
}

Set ith bit:

int setBit(int n, int i) {
return n | (1 << i);
}

Clear ith bit:

int clearBit(int n, int i) {
return n & ~(1 << i);
}

Toggle ith bit:

int toggleBit(int n, int i) {
return n ^ (1 << i);
}

boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}

complete single-page code with explanations and examples:

Use Cases

Efficient subset generation.
Storing boolean flags in an integer.
Fast parity checks.
Bitmask dynamic programming.
Power of two checks:

Summary Table

Concept	Time Complexity	Use Case / Importance
GCD (Euclidean Algorithm)	O(log(min(a, b)))	Simplify fractions, number theory
LCM	Depends on GCD	Synchronization, periodic tasks
Modular Arithmetic	O(1) per operation	Cryptography, hashing, combinatorics
Fast Power	O(log b)	Efficient exponentiation under modulus
Combinatorics (nCr, nPr)	Preprocessing O(n), Query O(1)	Counting problems, probability, permutations
Prefix Sum	O(n) preprocessing, O(1) queries	Range sum queries
Difference Array	O(1) range update	Range updates on arrays
Bit Manipulation	O(1) per operation	Flags, subsets, optimization, dynamic programming

100+ Assignments: Basics + Mathematics for DSA → Go TO End of This page to know more.

→ Next → CORE DATA STRUCTURES → Coming soon..

Follow Part→1 To …Part→N + Live Coding → Plan Simple

Techie Delight
HackerRank
HackerEarth
Codeforces
CodeChef
SPOJ
CSES Problem Set
AtCoder
TopCoder
CodinGame
CodingBat
UVa Online Judge
Kattis
CheckiO
CS50 (edX)
Project Euler
Exercism.io
Replit (Free Plan)
CS Dojo (YouTube + GitHub challenges)
Visualgo.net (DSA visualizer + quizzes)
GeeksforGeeks Practice (Basic tier)
Open DSA (Virginia Tech’s open DSA textbook + questions)
Advent of Code (Yearly puzzles in December)
Brilliant (Free tier)
FreeCodeCamp (Coding certifications + challenges)
MIT OCW (6.006, 6.0001, etc.)
Stanford CS106B Assignments (Available on GitHub)
100 Days of Code (GitHub + Twitter community)
CS50x (YouTube)
Python Tutor (Step-through code debugger)
The Odin Project
Nand2Tetris (Build a computer from scratch)
Rustlings (Rust language exercises)
JavaScript30 (30 mini projects, no libraries)
Frontend Mentor (Free challenges)
W3Schools (JS & Python code playgrounds)
Codewars (Free tier)
Codingame Clash of Code (Quick multiplayer coding)
CodeGym (Free Java lessons)
The Algorithms (GitHub repo of open DSA implementations)
OpenGenus IQ (Interview prep & knowledge base)
Bitburner (Coding game)
CodeCombat (Free up to certain levels)
Paiza.io (Online coding IDE + challenges)
LearnCpp.com Challenges
LeetCode
CoderByte
CodeSignal
InterviewBit
Pramp
Edabit
JetBrains Academy
Binary Search
Codewars (Premium kata explanations)
Frontend Mentor (Pro challenges)
Scrimba (Interactive code screencasts)
Codewell (Free + paid frontend challenges)
HackInScience (Python practice with feedback)
Programmr
Coding Ninjas Studio (Free + premium questions)
Scaler Topics (Some free DSA content)
AlgoExpert (Preview questions)
DevChallenges.io
Codepip (HTML/CSS games)
Skillrack (Free + college contests)
LearnDSA.io (Subset of Educative content)
Turing (Practice + job tests)
Code Avengers (Free trial)
Coding Minutes (Free samples from paid DSA courses)
Skillshare (Free for 1 month)
Udemy Coding Courses (Often free coupons)
Code.org (For younger learners, basic JavaScript)
Coding Hero (Freemium beginner problems)
Khan Academy – Computer Programming
ZTM Academy Free Challenges
LinkedIn Learning (Free month trial)
GeeksForGeeks Premium Courses (Some lessons free)
Platzi (Free coding basics)
ByteDegree (Intro tracks free)
Thinkful Coding Bootcamp (Free prep modules)
Educative.io (Grokking series)
ByteByteGo (System design)
DesignGurus.io
AlgoExpert
Ex-Facebook Interview Prep (Sean Prashad)
Turing Hut Challenges (Paid tracks)
Coursera Coding Specializations
Udacity Nanodegrees (DSA & System Design)
Pluralsight Coding Paths
Launch School
Treehouse (Techdegree programs)
Lambda School / BloomTech (Paid bootcamp)
Coding Dojo
Interview Cake
Fullstack Academy
Codesmith
Springboard (Career tracks)
Coding Blocks Online
Code Fellows
DataCamp (Python + Data Structures for DS)

Part 1: Time and Space Complexity (50+ assignments)

A. Concepts and Analysis

Explain Big-O notation with 5 original examples.
Explain Big-Theta notation with 3 original examples.
Explain Big-Omega notation with 3 original examples.
Analyze time complexity of linear search in best, average, and worst cases.
Analyze time complexity of binary search in best, average, and worst cases.
Analyze space complexity of recursive Fibonacci.
Calculate time complexity of bubble sort in all cases.
Calculate time complexity of insertion sort in all cases.
Calculate time complexity of merge sort.
Calculate time complexity of quicksort and explain pivot choice effects.
Calculate space complexity of merge sort.
Compare space vs time trade-off in merge sort vs quicksort.
Time complexity of a balanced binary search tree operations.
Explain amortized time complexity with stack push/pop.
Calculate time complexity for matrix multiplication naive approach.
Calculate time complexity for matrix multiplication using Strassen’s algorithm.
Explain why hashmap operations are average O(1) but worst-case O(n).
Calculate time complexity of naive substring search.
Calculate time complexity of KMP substring search.
Explain how caching (memoization) improves time complexity for Fibonacci.
Analyze time complexity of DFS and BFS on graphs.
Calculate space complexity of DFS and BFS.
Analyze time complexity of Dijkstra’s shortest path algorithm.
Analyze space complexity of Dijkstra’s algorithm.
Calculate complexity of Prim’s and Kruskal’s MST algorithms.
Explain time complexity of heap operations.
Implement and analyze complexity of priority queue insert/extract.
Calculate time complexity of n-queens problem brute force.
Calculate time complexity of backtracking Sudoku solver.
Analyze recursive vs iterative factorial time and space complexity.
Explain complexity of exponentiation by squaring.
Compare iterative vs recursive binary search.
Analyze complexity of array vs linked list insertion/deletion.
Calculate complexity of dynamic array resizing.
Explain time complexity of hash collision resolution methods (chaining, open addressing).
Analyze space complexity of trie data structure.
Calculate time complexity of radix sort.
Compare time complexity of different sorting algorithms on nearly sorted data.
Calculate complexity of counting sort.
Analyze worst-case scenario for quicksort.
Explain time-space trade-offs with example of lookup tables.
Analyze time complexity of substring search with Rabin-Karp.
Calculate complexity of finding duplicates using sorting vs hashing.
Analyze the complexity of string reversal.
Explain time complexity of palindrome checking.
Calculate time complexity of all pairs shortest path (Floyd-Warshall).
Compare complexity of BFS vs DFS for cycle detection.
Calculate complexity of dynamic programming solutions for Fibonacci.
Explain time complexity of topological sort.
Analyze complexity of graph coloring heuristics.

Part 2: Mathematics for DSA (50+ assignments)

Prime Numbers and Sieve

Implement and analyze sieve of Eratosthenes for primes up to 10^5.
Modify sieve to return prime count up to N.
Find sum of primes up to 10^6 using sieve.
Count twin primes up to 10^6.
Implement naive prime checker using trial division.
Compare sieve and naive prime checker performance.
Implement segmented sieve for range [L, R].
Use sieve to factorize numbers up to 10^6.
Find largest prime factor of a number using sieve.
Implement prime checking using Miller-Rabin test.
Generate all primes between 1 and 10^7 using sieve.
Find prime gaps between consecutive primes up to 10^6.
Find first 100 primes.
Find sum of first N primes.
Check if number is perfect square of a prime.
Find primes in arithmetic progression using sieve.
Count prime numbers in a large interval efficiently.
Calculate product of primes up to N modulo M.
Implement Eratosthenes sieve with bitset optimization.
Find the smallest prime factor for all numbers up to N.
Check Goldbach’s conjecture for even numbers up to 10^6.
Find number of primes with digit sum equal to X.
Find primes with palindrome property.
Find next prime number after N.
Calculate Euler’s Totient function for numbers up to N.
Calculate GCD using Euclidean Algorithm.
Implement Extended Euclidean Algorithm.
Solve linear Diophantine equations using extended Euclidean.
Calculate LCM using GCD.
Implement fast modular exponentiation.
Use modular exponentiation to compute large powers modulo M.
Calculate modular inverse using Fermat’s little theorem.
Implement combinatorial nCr using Pascal’s triangle.
Precompute factorials and inverse factorials modulo M for fast nCr.
Implement Lucas theorem for large nCr modulo prime.
Use prefix sums to answer range sum queries.
Implement difference array for range update and point query.
Use prefix sums in 2D arrays.
Solve subarray sum problems using prefix sums.
Implement bit manipulation for counting set bits.
Use bit manipulation to generate all subsets of a set.
Implement Brian Kernighan’s algorithm for bit counting.
Use bitmask DP to solve subset sum problem.
Find XOR of all elements in an array.
Implement left and right bit shifts and explain effect.
Solve problems involving checking power of two using bits.
Implement and explain combinatorial permutations (nPr).
Calculate number of derangements for n elements.
Solve problems combining prefix sums and combinatorics.
Explain how modular arithmetic applies to hash functions.

Optional stretch tasks

Implement segmented sieve for prime factorization on huge ranges.
Use sieve to solve prime factor queries online.
Implement multiplicative inverse using extended Euclidean.
Create a mini library for modular arithmetic (add, subtract, multiply, divide).
Compare iterative vs recursive factorial with memoization.
Optimize prefix sums for dynamic arrays.
Use Fenwick tree or Segment tree to answer prefix sum queries with updates.
Implement fast exponentiation for matrices.
Explore connections between combinatorics and probability in algorithms.
Solve classic combinatorial puzzles using code (e.g., Catalan numbers).

PHASE 1: Basic Recursion (Understanding the Flow)

Goal: Understand base case, recursive case, and how call stack works

Assignments:

Print Numbers 1 to N and N to 1 (both ways)
Factorial of N
Sum of Digits of a Number
Fibonacci Series (basic recursive)
Power of a Number (a^b)

PHASE 2: Intermediate Recursion (Strings, Arrays, Backtracking Intro)

Goal: Practice recursion with decisions and branching

Assignments:

Reverse a String using Recursion
Check if String is Palindrome
Find Max/Min in an Array Recursively
Check if Array is Sorted
Linear Search in Array using Recursion

PHASE 3: Advanced Recursion (Combinatorics & Backtracking Base)

Goal: Solve subset problems, string operations, and decision trees

Assignments:

Generate All Subsets of Array/String (Power Set)
Generate All Permutations of a String
Count Paths in Grid (Right/Down only)
Print All Balanced Parentheses (n pairs)
String to Integer Conversion using Recursion

PHASE 4: Recursive + Optimization Concepts

Goal: Merge recursion with optimization (divide & conquer, pruning, memoization)

Assignments:

Binary Search using Recursion
Merge Sort using Recursion
Quick Sort using Recursion
Tower of Hanoi
Generate All Binary Strings Without Consecutive 1s

PHASE 5: Real-World Recursive Challenges

Goal: Solve deep recursive problems asked in interviews and competitive coding

Assignments:

Josephus Problem
Letter Combinations of a Phone Number (like keypad input)
Generate All Palindromic Partitions
Subset Sum Problem
Word Break (check if string can be segmented using dictionary)

Practice Set:

Visualizer: https://pythontutor.com/
Java Debugger in VS Code/IntelliJ: Trace recursive call stack
GeeksForGeeks: Recursion practice problems
LeetCode: Easy → Medium tagged with "recursion"

Optional Challenges

Convert Recursive to Iterative (Tail Recursion Conversion)
Solve problems using Memoization (Top-Down DP)
Track Recursive Tree using logging:

PHASE 1: Basic Backtracking (Foundation Level)

Goal: Understand recursion + backtracking flow (choose → explore → un-choose)

Assignments:

Subset Sum (Yes/No)
- Check if a subset exists with given sum.
Generate All Subsets (Power Set)
- Input: [1, 2, 3] → Output: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
String Permutations
- Input: "ABC" → Output: "ABC", "ACB", "BAC", ..."
Palindrome Partitioning
- Input: "aab" → Output: [[a, a, b], [aa, b]]
Rat in a Maze (4 directions)
- Maze of 1s and 0s, find all paths from top-left to bottom-right.

PHASE 2: Intermediate Backtracking (Constraint Solving)

Goal: Solve constraint-based branching problems using recursion

Assignments:

N-Queens Problem
- Place N queens on N×N board such that no two attack each other.
Sudoku Solver
- Fill a partially completed 9x9 grid following Sudoku rules.
Word Search in 2D Grid
- Search word from a 2D board using DFS/backtracking.
Unique Permutations with Duplicates
- Input: [1, 1, 2] → Avoid duplicate permutations.
Combination Sum (1 & 2)
- Find all combinations of numbers that sum to a target.

PHASE 3: Advanced Backtracking (Optimization + Pruning)

Goal: Combine backtracking with smart pruning, optimization, and state tracking

Assignments:

Knight’s Tour Problem
- Visit every square once with knight's L-shaped moves.
Solve M-Coloring of Graph
- Color graph vertices with at most M colors such that no adjacent share color.
Word Break II
- Given a string and dictionary, return all valid sentence combinations.
Expression Add Operators
- Input: "123", target=6 → Output: ["1+2+3", "1*2*3"]
Tug of War (Partition array into two balanced subsets)
- Minimize diff of two subsets.

PHASE 4: Expert Challenges (Interview-Style)

Goal: Apply deep recursion with optimization, bitmasking, and memoization

Assignments:

Restore IP Addresses
- Input: "25525511135" → Output: All valid IPs.
Match Regular Expression (., *)
- Implement regex engine with backtracking.
Robot Room Cleaner (Leetcode Hard)
- Robot moves in unknown grid, must clean every accessible cell.
Minimum Number of Squares (Integer Partition)
- Example: 12 = 4+4+4 or 9+1+1+1... → find minimum count.
Travelling Salesman Problem (TSP) using Backtracking + Bitmasking
- Find minimum path visiting all cities.

Practice Sets:

Leetcode: Backtracking Tag
HackerRank: Recursion and Backtracking
GeeksForGeeks: Backtracking Problems
Codeforces: Search for "constructive algorithms" or "dfs + bitmask"

Tools for Learning:

Draw recursion tree on paper.
Use breakpoints/debugger to trace call stack.
Log parameters in each call: System.out.println("i=" + i + ", path=" + path);

Phase 1: Basics (1D DP)

Learn fundamentals like state transition, base case, and 1D dp[]

Fibonacci Number
Climbing Stairs
Min Cost Climbing Stairs
House Robber
Maximum Sum of Non-Adjacent Elements
Decode Ways (A=1, B=2...)
Jump Game I (Can reach end?)
Jump Game II (Min jumps to end)

Phase 2: Subset / Knapsack DP (2D DP)

Practice problems with dp[i][j] pattern

0/1 Knapsack
Subset Sum
Equal Subset Partition
Count Subsets with Given Sum
Target Sum
Perfect Sum Problem
Partition with Minimum Absolute Difference

Phase 3: String & LCS Based DP

Work on problems with dp[i][j] based on two strings

Longest Common Subsequence (LCS)
Longest Palindromic Subsequence
Longest Palindromic Substring
Edit Distance
Shortest Common Supersequence
Sequence Pattern Matching
Wildcard Matching
Regular Expression Matching

Phase 4: Grid & Coin Problems

Learn tabulation across grids and combinations

Unique Paths
Unique Paths II (with obstacles)
Minimum Path Sum
Coin Change 1 (Min coins to make value)
Coin Change 2 (Number of ways to make value)
Gold Mine Problem
Cherry Pickup (advanced grid DP)

Phase 5: Partition & Palindrome Problems

Focus on splitting and recursive subproblem DP

Palindrome Partitioning
Palindrome Partitioning II (Min cuts)
Boolean Parenthesization
Matrix Chain Multiplication
Evaluate Expression to True
Burst Balloons

Phase 6: Advanced Topics

Covers DP on trees, memory optimization, and hard state transitions

Egg Dropping Puzzle
Painting Houses / Fences
Job Scheduling with Profits
Digit DP (Count numbers with constraints)
LIS (Longest Increasing Subsequence)
DP on Trees (subtree sums, max path sum, etc.)
DP + Bitmask (Travelling Salesman, N-Queens)
K-th Order Statistics in Arrays (Bonus)

Platform-wise DP Resources

1. LeetCode

🔗 Dynamic Programming Tag
Must-do:
- 198. House Robber
- 1. Coin Change
- 1. Longest Common Subsequence
- 1. Longest Increasing Subsequence
- 1. Egg Drop
Premium-only: Harder DP like Wildcard Matching, Burst Balloons

2. GeeksforGeeks (GFG)

Dynamic Programming Topic
Beginner Friendly + Editorials
Best for:
- 0/1 Knapsack variants
- Subset Sum
- Boolean Parenthesization
- Matrix Chain Multiplication
- Palindrome Partitioning
Offers “GFG 100 Must Solve DP Problems”

3. Codeforces

DP Problems Tag
Contest Style, Time-bound
Best for:
- Digit DP
- Bitmask DP
- DP on Trees
- Optimization via Convex Hull / Binary Search
Use CF when you're done with LeetCode-style problems

4. AtCoder

Educational DP Contest (A-Z)
Highly recommended series to master 1D, 2D, Knapsack, Tree DP
26 problems (A to Z): increasing difficulty
Start here after Phase 3

5. InterviewBit

DP Track
Good for Interview Prep
Covers: LCS, LIS, Edit Distance, Regex Matching
Offers time-bound “progressive levels”

6. HackerRank

DP Practice Problems
Good tutorials for:
- Coin Change
- Candies Distribution
- Decoding Ways
- Stocks Buy & Sell Problems
Ideal for understanding “base case” focused tabulation

7. Coding Ninjas / Coding Studio

Top 50 DP Problems List
Offers company-wise practice (Amazon, Flipkart, etc.)

8. CodeChef

DP Tag
Advanced & Contest‑oriented (competitive)
Bitmask, Digit DP, Memory Optimization challenges

Code

Coding To 1Cr ~ Nitesh Synergy

Pease check git repo code & research 1Cr Problem Statements & Solutions

https://github.com/niteshsynergy/DSA_Phase1

https://github.com/niteshsynergy/DSA_Phase2

https://github.com/niteshsynergy/DSA_Phase3

https://github.com/niteshsynergy/Code1CrPlusMission

https://github.com/niteshsynergy/ResearchProblemsCoding1CrPlus

https://github.com/niteshsynergy/techassign/

DSA To 1Cr Coding~ Notes Available ~ Offline + Github

DSA Weekly Syllabus :

What is DSA (Data Structures and Algorithms)?

Why DSA is Needed

Types of Data Structures (DS)

1. Linear Data Structures

2. Non-Linear Data Structures

3. Hash-Based Structures

Types of Algorithms (A)

1. Searching Algorithms

2. Sorting Algorithms

3. Recursion & Backtracking

4. Dynamic Programming (DP)

5. Greedy Algorithms

6. Divide and Conquer

7. Graph Algorithms

1. Time and Space Complexity

What is Time Complexity?

What is Space Complexity?

Part 1: Big-O, Big-Theta, Big-Omega

Big-O (O) – Worst-case

Big-Omega (Ω) – Best-case

Big-Theta (Θ) – Tight bound

Part 2: Best, Average, Worst Case

Why Case Analysis Matters:

Example: Linear Search

Part 3: Common Time Complexities (With Examples)

Part 4: Space vs Time Trade-offs

Example: Caching / Memoization

Real-Life Examples

2. Mathematics for DSA

Prime Numbers — Sieve of Eratosthenes (In-Depth)

What is a Prime Number?

Why Are Prime Numbers Important in DSA?

Brute Force Approach: Primality Check

Time Complexity: O(√n)

Sieve of Eratosthenes

Purpose:

Core Idea:

Steps:

Time Complexity Analysis:

Space Complexity:

Visual Walkthrough: N = 30

Optimizations

Sieve from i * i instead of 2*i

Segmented Sieve

What is GCD & LCM?

Euclidean Algorithm for GCD

Problem: Find GCD of two numbers

How it works for gcd(48, 18):

How it works for gcdIter(48, 18):

LCM Using GCD

Code:

Example: Calculate LCM(48, 18)

Verification:

Modular Arithmetic

What?

Why?

Common Operations

Power Exponentiation (Fast Power)

Problem:

Naive:

Fast Exponentiation:

Code (Recursive):

Example: Calculate 313mod 173^{13} \mod 17 3 13 mod 17

Step-by-step trace:

Returning back:

Final result:

Time Complexity:

Combinatorics (nCr, nPr)

Definitions:

Time Complexity: `O(√n)`

Visual Walkthrough: `N = 30`

Sieve from `i * i` instead of `2*i`

Example: Calculate $313mod 173^{13} \mod 17$ $3$ $13$ $mod$ $17$

Example: Calculate $(52)mod 1,000,000,007\binom{5}{2} \mod 1,000,000,007$ $($ $25$ $$ $)$ $mod$ $1$ $,$ $000$ $,$ $000$ $,$ $007$

Step 2: Query sums using `rangeSum`