Divide and Conquer Strategy and Recurrence Relations in DSA Typescript - Build from Scratch

Divide and Conquer Strategy and Recurrence Relations

📖 Scenario: Imagine you have a large list of numbers representing daily sales in a store. You want to find the total sales quickly by splitting the list into smaller parts, adding each part, and then combining the results.

🎯 Goal: Build a simple divide and conquer function in TypeScript that sums numbers in an array by splitting it into halves recursively. Understand how the problem breaks down and how the recurrence relation describes the time complexity.

📋 What You'll Learn

Create an array called sales with exactly these numbers: [10, 20, 30, 40, 50, 60, 70, 80]

Create a variable called threshold and set it to 2

Write a recursive function called sumSales that takes an array of numbers and returns their sum using divide and conquer:

sumSales should return the sum directly if the array length is less than or equal to threshold

Otherwise, split the array into two halves, recursively sum each half, and return their sum

Print the result of calling sumSales on the sales array

💡 Why This Matters

🌍 Real World

Divide and conquer is used in many algorithms like sorting, searching, and multiplying large numbers efficiently.

💼 Career

Understanding divide and conquer helps in designing efficient algorithms and solving complex problems in software development.

1

Create the sales data array

Create an array called sales with these exact numbers: [10, 20, 30, 40, 50, 60, 70, 80]

DSA Typescript

# Your code here

Hint

Use const sales: number[] = [...] to create the array with the exact numbers.

2

Set the threshold for direct sum

Create a variable called threshold and set it to 2

DSA Typescript

const sales: number[] = [10, 20, 30, 40, 50, 60, 70, 80];
# Your code here

Hint

Use const threshold: number = 2; to set the threshold.

3

Write the divide and conquer sum function

Write a recursive function called sumSales that takes an array of numbers called arr and returns their sum using divide and conquer. If arr.length is less than or equal to threshold, return the sum directly using a loop. Otherwise, split arr into two halves, recursively call sumSales on each half, and return their sum.

DSA Typescript

const sales: number[] = [10, 20, 30, 40, 50, 60, 70, 80];
const threshold: number = 2;

# Your code here

Hint

Use recursion with a base case for small arrays and split the array for larger ones.

4

Print the total sales using sumSales

Print the result of calling sumSales on the sales array using console.log

DSA Typescript

const sales: number[] = [10, 20, 30, 40, 50, 60, 70, 80];
const threshold: number = 2;

function sumSales(arr: number[]): number {
    if (arr.length <= threshold) {
        let total = 0;
        for (let i = 0; i < arr.length; i++) {
            total += arr[i];
        }
        return total;
    } else {
        const mid = Math.floor(arr.length / 2);
        const leftSum = sumSales(arr.slice(0, mid));
        const rightSum = sumSales(arr.slice(mid));
        return leftSum + rightSum;
    }
}

# Your code here

Hint

Use console.log(sumSales(sales)); to print the total sum.