PROBLEM SOLVING - DIVIDE AND CONQUER IN C

Divide and Conquer Basics

Divide and Conquer Definition

Divide and Conquer is an algorithm design paradigm that works by recursively breaking down a problem into subproblems until they become simple enough to be solved directly. Key characteristics:

Divide - Break the problem into smaller subproblems
Conquer - Solve the subproblems recursively
Combine - Combine the solutions to solve the original problem

Divide and Conquer Applications

Divide and Conquer is fundamental in computer science with various applications:

Sorting algorithms (Merge Sort, Quick Sort)
Searching algorithms (Binary Search)
Mathematical computations (Matrix multiplication)
Computational geometry (Closest pair of points)
Fast Fourier Transform (FFT)
Karatsuba algorithm for fast multiplication

General Approach

The typical structure of a Divide and Conquer algorithm:

function divideAndConquer(problem) {
    if (problem is small enough) {
        solve it directly
    } else {
        divide problem into smaller subproblems
        conquer each subproblem by calling divideAndConquer
        combine the solutions
    }
}

PROBLEM SOLVING - DIVIDE AND CONQUER TRICKS

#	Technique	Use Case	Approach	Complexity	Examples
1	Merge Sort	Sorting arrays or linked lists	Divide array into halves, sort each half, then merge	O(n log n)	Sorting large datasets External sorting Inversion count
2	Quick Sort	Efficient in-memory sorting	Choose pivot, partition array, recursively sort partitions	O(n log n) avg O(n²) worst	General purpose sorting Kth smallest element Top K elements
3	Binary Search	Searching in sorted arrays	Repeatedly divide search interval in half	O(log n)	Finding elements Finding boundaries Rotated array search
4	Closest Pair	Find two closest points in 2D plane	Divide plane into halves, find closest in each, check strip	O(n log n)	Computational geometry Collision detection Nearest neighbor
5	Strassen's Matrix	Matrix multiplication	Divide matrices into submatrices, multiply recursively	O(n^2.81)	Large matrix operations Graphics processing Scientific computing
6	Karatsuba	Fast multiplication of large numbers	Break numbers into parts, multiply recursively	O(n^1.585)	Big integer multiplication Cryptography Arbitrary precision
7	Max Subarray	Find contiguous subarray with max sum	Divide array, find max in left, right, and crossing	O(n log n)	Stock market analysis Signal processing Data analysis

Common Divide and Conquer Implementations

Merge Sort Implementation

void merge(int arr[], int l, int m, int r) {
    // Merges two subarrays
    // Implementation details...
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

Time Complexity: O(n log n)

Quick Sort Implementation

int partition(int arr[], int low, int high) {
    // Partition logic...
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Time Complexity: O(n log n) avg

Binary Search Implementation

int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (arr[m] == x) return m;
        if (arr[m] < x) l = m + 1;
        else r = m - 1;
    }
    return -1;
}

Time Complexity: O(log n)

Advanced Divide and Conquer Techniques

#	Technique	Description	Use Case
1	Convex Hull	Algorithm to find the smallest convex polygon containing all points	Computational geometry
2	Fast Fourier Transform	Efficient algorithm to compute the Discrete Fourier Transform	Signal processing, polynomial multiplication
3	Strassen's Algorithm	Divide and conquer method for matrix multiplication	Large matrix operations
4	Karatsuba Algorithm	Fast multiplication algorithm for large numbers	Cryptography, big number arithmetic
5	Closest Pair Problem	Finding the two closest points in a set of points in 2D plane	Computational geometry

Related Algorithm Resources

Sorting Algorithms

Search Algorithms

Dynamic Programming

Recursion