Module 1: Programming Foundations

1. What is Problem Solving?

Definition

Problem solving in programming is the ability to understand a problem, break it into smaller parts, choose the right logic and data structures, and convert that logic into efficient code.

Coding is not about typing syntax. Coding is about thinking, decision-making, and optimization.

Problem Solving Flow

A strong problem solver follows a clear mental process:

• Understand the problem clearly (inputs, outputs, rules)
• Identify patterns or repetitions
• Decide the approach (brute force, optimized, recursion, greedy, etc.)
• Write clean logic
• Analyze time and space complexity
• Code and test with edge cases

Example

Problem: Given an array, find the maximum element.

Thinking process:

• Traverse the array once
• Compare each element with the current maximum

int max = arr[0];
for(int i = 1; i < n; i++){
    if(arr[i] > max){
        max = arr[i];
    }
}

This solution is simple, efficient, and scalable.

---

2. Time & Space Complexity (Big-O, Big-Ω, Big-Θ)

Why Complexity Matters

Time and space complexity help us understand how an algorithm behaves as input size grows. In competitive programming and interviews, inefficient solutions often fail due to time limit exceeded (TLE) or memory limit exceeded (MLE).

Time Complexity

Time complexity measures how execution time increases with input size n.

Big-O Notation (Worst Case)

Big-O represents the maximum time an algorithm may take.

Example: Linear Search

for(int i = 0; i < n; i++){
    if(arr[i] == key) return i;
}

Worst case: element found at the last index
Time Complexity: O(n)

Big-Ω Notation (Best Case)

Big-Ω represents the minimum time required.

Example: Key found at index 0
Time Complexity: Ω(1)

Big-Θ Notation (Average Case)

Big-Θ represents the tight bound, showing average performance.

Example: Element found in the middle
Time Complexity: Θ(n)

Common Time Complexities

• O(1): Constant time
• O(log n): Binary search
• O(n): Linear traversal
• O(n log n): Merge sort
• O(n²): Nested loops
• O(2ⁿ): Exponential (inefficient)

Space Complexity

Space complexity measures memory usage, including variables, arrays, and recursion stack.

Example:

int a = 10;           // O(1)
int[] arr = new int[n]; // O(n)

---

3. Worst, Best & Average Case Analysis

Why Case Analysis is Important

Worst-case analysis ensures the solution won’t fail under extreme conditions. Best case shows potential efficiency. Average case reflects real-world performance.

Example: Bubble Sort

• Best case (already sorted): O(n)
• Average case: O(n²)
• Worst case (reverse sorted): O(n²)

Example: Binary Search

• Best case: O(1)
• Average case: O(log n)
• Worst case: O(log n)

---

4. Recursion Basics

What is Recursion?

Recursion is a technique where a function calls itself to solve a smaller version of the same problem.

Two Essential Components

• Base case: Stops recursion
• Recursive case: Breaks the problem into smaller parts

Example: Factorial

int factorial(int n){
    if(n == 0) return 1;
    return n * factorial(n - 1);
}

How Recursive Thinking Works

You trust the function to solve smaller inputs and focus on combining results.

Stack Memory

Each recursive call occupies stack memory.

Factorial time complexity: O(n)
Factorial space complexity: O(n) due to recursion stack

---

5. Mathematical Thinking for DSA

Why Math Matters

Mathematics helps reduce brute-force solutions, optimize loops, and handle large constraints efficiently.

Key Mathematical Concepts

• Modulo arithmetic
• GCD and LCM
• Prime numbers
• Logarithms
• Number patterns
• Bit manipulation

Example: Sum of First N Numbers

Brute force approach:

int sum = 0;
for(int i = 1; i <= n; i++){
    sum += i;
}

Time complexity: O(n)

Optimized approach:

int sum = n * (n + 1) / 2;

Time complexity: O(1)

Example: Check Even or Odd Using Bitwise

if((n & 1) == 0){
    System.out.println("Even");
}

---

6. Input and Output Handling for Competitive Programming

Why Efficient I/O is Crucial

Competitive programming often involves large input sizes. Slow input/output methods can cause TLE even with correct logic.

Fast Input in Java

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");

Fast Output

StringBuilder sb = new StringBuilder();
sb.append(result);
System.out.print(sb);

Example: Reading an Array

int n = Integer.parseInt(br.readLine());
String[] arr = br.readLine().split(" ");

Best Practices

• Avoid using Scanner
• Minimize print statements
• Use buffered input/output

---

7. Constraints Reading & Optimization Mindset

Why Constraints Control the Solution

Constraints tell you which algorithm is feasible and which will fail.

Constraint to Algorithm Mapping

• n ≤ 10⁵ → O(n) or O(n log n)
• n ≤ 10⁶ → O(n)
• n ≤ 10³ → O(n²)
• n ≤ 100 → O(n³)

Example

If n = 10⁵
O(n²) will fail
O(n log n) will pass

Optimization Mindset

• Reduce nested loops
• Use prefix sums
• Precompute results
• Choose correct data structures
• Replace brute force with math

Example: Prefix Sum

prefix[i] = prefix[i - 1] + arr[i];