# Using Loops (Iterative Method)
#Time Complexity: O(n) Space Complexity: O(1)
arr = [1, 2, 3, 4, 5]
total = 0
for num in arr:
  total += num
print("Sum of array elements =", total)

# Recursive Method
# Time Complexity: O(n) — each element is processed
# Space Complexity: O(n) — recursive call stack stores at most n calls
def sum_recursive(arr, n):
  if n == 0:
    return 0
  return arr[n-1] + sum_recursive(arr, n-1)
arr = [1, 2, 3, 4, 5]
print("Sum (recursive) =", sum_recursive(arr, len(arr)))

# Recursive Divide and Conquer Sum
#Time Complexity: O(n)
#Space Complexity: O(log n) — height of recursion tree
def sum_divide_conquer(arr, left, right):
  if left == right:
    return arr[left]
  mid = (left + right) // 2
  left_sum = sum_divide_conquer(arr, left, mid)
  right_sum = sum_divide_conquer(arr, mid + 1, right)
  return left_sum + right_sum
arr = [1, 2, 3, 4, 5]
print("Sum (divide & conquer) =", sum_divide_conquer(arr, 0, len(arr) - 1)))