विभाजित करें और जीतें का खाका

# Divide and Conquer vs DP:
# D&C: sub-problems are INDEPENDENT (no overlap)
# DP:  sub-problems OVERLAP (same sub-problem solved multiple times)

# D&C examples:
# Merge sort: split array in half, sort each, merge
# Binary search: check midpoint, recurse on one half
# Max subarray (D&C): find max in left half, right half, crossing

# Recurrence pattern:
# T(n) = 2T(n/2) + O(n) → O(n log n)  [merge sort]
# T(n) = T(n/2) + O(1) → O(log n)     [binary search]
# T(n) = T(n/k) + O(n) → O(n log_k n) [k-way split]

def divide_and_conquer(arr, lo, hi):
    # BASE CASE: trivial sub-problem
    if lo >= hi:
        return base_case_result(arr, lo, hi)
    
    # DIVIDE: split at midpoint
    mid = (lo + hi) // 2
    
    # CONQUER: solve sub-problems recursively
    left_result  = divide_and_conquer(arr, lo, mid)
    right_result = divide_and_conquer(arr, mid + 1, hi)
    
    # COMBINE: merge results
    return combine(left_result, right_result, arr, lo, mid, hi)

def base_case_result(arr, lo, hi): return arr[lo]
def combine(l, r, arr, lo, mid, hi): return max(l, r)

def merge_sort(arr):
    # BASE CASE
    if len(arr) <= 1:
        return arr
    # DIVIDE
    mid = len(arr) // 2
    # CONQUER
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    # COMBINE
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

print(merge_sort([5, 3, 8, 1, 9, 2]))  # [1,2,3,5,8,9]

# Master Theorem quick examples:
# T(n) = 2T(n/2) + O(n)    → a=2,b=2,f=n,n^log2(2)=n → Case2 → O(n log n)
# T(n) = 2T(n/2) + O(1)    → a=2,b=2,f=1,n^1=n >> 1  → Case1 → O(n)
# T(n) = 2T(n/2) + O(n^2)  → a=2,b=2,f=n^2,n^1 << n^2 → Case3 → O(n^2)
# T(n) = T(n/2) + O(1)     → a=1,b=2,f=1,n^log2(1)=1=f → Case2 → O(log n)
# T(n) = T(n/3)+T(2n/3)+O(n) → Master doesn't apply directly → O(n log n) by recursion tree

recurrences = [
    ('Merge sort: 2T(n/2)+n', 'O(n log n)'),
    ('Binary search: T(n/2)+1', 'O(log n)'),
    ('Naive matrix mult: 8T(n/2)+n^2', 'O(n^3)'),
    ('Strassen: 7T(n/2)+n^2', 'O(n^2.81)'),
]
for r, sol in recurrences: print(r, '->', sol)

def max_subarray_dc(nums, lo=None, hi=None):
    if lo is None: lo, hi = 0, len(nums) - 1
    if lo == hi: return nums[lo]
    mid = (lo + hi) // 2
    # Conquer
    left_max  = max_subarray_dc(nums, lo, mid)
    right_max = max_subarray_dc(nums, mid + 1, hi)
    # Cross-midpoint sum
    left_sum = curr = 0
    for i in range(mid, lo - 1, -1):
        curr += nums[i]
        left_sum = max(left_sum, curr)
    right_sum = curr = 0
    for i in range(mid + 1, hi + 1):
        curr += nums[i]
        right_sum = max(right_sum, curr)
    cross_max = left_sum + right_sum
    return max(left_max, right_max, cross_max)

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_dc(nums))  # 6

def my_pow(x, n):
    if n < 0:
        return 1 / my_pow(x, -n)
    # BASE CASE
    if n == 0: return 1
    # DIVIDE and CONQUER
    half = my_pow(x, n // 2)
    if n % 2 == 0:
        return half * half          # even: x^n = (x^(n/2))^2
    else:
        return x * half * half      # odd: x^n = x * (x^(n/2))^2

print(my_pow(2, 10))   # 1024
print(my_pow(2, -2))   # 0.25
print(my_pow(3, 5))    # 243
print(my_pow(0, 0))    # 1

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sorted_array_to_bst(nums):
    def helper(lo, hi):
        if lo > hi: return None
        mid = (lo + hi) // 2
        node = TreeNode(nums[mid])    # DIVIDE at midpoint
        node.left  = helper(lo, mid - 1)  # CONQUER left
        node.right = helper(mid + 1, hi)  # CONQUER right
        # COMBINE: already done by assignment
        return node
    return helper(0, len(nums) - 1)

def inorder(node):
    if not node: return []
    return inorder(node.left) + [node.val] + inorder(node.right)

root = sorted_array_to_bst([-10, -3, 0, 5, 9])
print(inorder(root))  # [-10,-3,0,5,9] (sorted, proving BST property)

# When D&C hurts:
# Fibonacci with pure D&C (no memo): T(n) = T(n-1) + T(n-2) → O(2^n)
# Sub-problems OVERLAP → use DP or memoisation instead

def fib_dc(n):
    if n <= 1: return n
    return fib_dc(n-1) + fib_dc(n-2)  # O(2^n)!

def fib_dp(n):
    a, b = 0, 1
    for _ in range(n): a, b = b, a+b
    return a  # O(n)

print(fib_dp(30))  # fast
# fib_dc(40) would take seconds — do not run large values!

def search_matrix(matrix, target):
    if not matrix: return False
    m, n = len(matrix), len(matrix[0])
    row, col = 0, n - 1  # start top-right
    while row < m and col >= 0:
        val = matrix[row][col]
        if val == target:
            return True
        elif val > target:
            col -= 1  # eliminate this column
        else:
            row += 1  # eliminate this row
    return False

matrix = [
    [1,   4,  7, 11, 15],
    [2,   5,  8, 12, 19],
    [3,   6,  9, 16, 22],
    [10, 13, 14, 17, 24],
    [18, 21, 23, 26, 30]
]
print(search_matrix(matrix, 5))   # True
print(search_matrix(matrix, 20))  # False

# Merge sort recursion tree analysis:
# Level 0: 1 problem of size n → O(n) work
# Level 1: 2 problems of size n/2 → 2*O(n/2) = O(n) work
# Level 2: 4 problems of size n/4 → 4*O(n/4) = O(n) work
# ...
# Level log(n): n problems of size 1 → n*O(1) = O(n) work
# Total levels = log(n)+1
# Total work = O(n) * O(log n) = O(n log n)

import math
n = 64
levels = int(math.log2(n)) + 1
print(f'n={n}: {levels} levels, {n}*{levels} = {n*levels} work units')
print(f'O(n log n) = O({n} * {int(math.log2(n))}) = O({n*int(math.log2(n))})')

# D&C interview template to memorize:
def dc_template(problem, lo, hi):
    # 1. BASE CASE (state it first)
    if lo == hi: return solve_base(problem, lo)
    # 2. DIVIDE
    mid = (lo + hi) // 2
    # 3. CONQUER
    left  = dc_template(problem, lo, mid)
    right = dc_template(problem, mid + 1, hi)
    # 4. COMBINE (this is where the algorithm-specific logic goes)
    return combine_results(left, right, problem, lo, mid, hi)

def solve_base(p, i): return p[i]
def combine_results(l, r, p, lo, mid, hi): return max(l, r)

print('D&C template: base-divide-conquer-combine')
print('Complexity usually: T(n)=2T(n/2)+O(n) → O(n log n)')