Why Divide and Conquer and What It Gives You in DSA Typescript - See It Work

Why Divide and Conquer and What It Gives You

📖 Scenario: Imagine you have a big box of mixed colored balls. You want to count how many balls of each color are there. Instead of counting all at once, you decide to split the box into smaller boxes, count each smaller box, and then add the counts together. This is like using the divide and conquer approach.

🎯 Goal: You will build a simple program that uses the divide and conquer method to count the total number of balls in a list by splitting the list into halves until small enough to count directly, then combining the counts.

📋 What You'll Learn

Create an array called balls with exactly these numbers: 5, 3, 8, 6, 2, 7, 4, 1

Create a variable called threshold and set it to 2

Write a recursive function called countBalls that takes an array of numbers and returns the total count using divide and conquer

Print the total count returned by countBalls(balls)

💡 Why This Matters

🌍 Real World

Divide and conquer is used in sorting large lists, searching data quickly, and solving complex problems by breaking them into smaller, easier tasks.

💼 Career

Understanding divide and conquer helps in software development roles that require efficient algorithms, such as backend development, data engineering, and algorithm design.

1

Create the initial data array

Create an array called balls with these exact numbers: 5, 3, 8, 6, 2, 7, 4, 1

DSA Typescript

# Create the array balls with the given numbers
// Your code here

Hint

Use const balls = [5, 3, 8, 6, 2, 7, 4, 1]; to create the array.

2

Set the threshold for direct counting

Create a variable called threshold and set it to 2

DSA Typescript

const balls = [5, 3, 8, 6, 2, 7, 4, 1];
// Create the threshold variable and set it to 2
// Your code here

Hint

Use const threshold = 2; to set the threshold.

3

Write the divide and conquer counting function

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

DSA Typescript

const balls = [5, 3, 8, 6, 2, 7, 4, 1];
const threshold = 2;
// Write the recursive function countBalls below
// Your code here

Hint

Use recursion to split the array until small enough, then count directly.

4

Print the total count of balls

Print the total count returned by calling countBalls(balls)

DSA Typescript

const balls = [5, 3, 8, 6, 2, 7, 4, 1];
const threshold = 2;

function countBalls(arr: number[]): number {
    if (arr.length <= threshold) {
        return arr.length;
    }
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);
    return countBalls(left) + countBalls(right);
}

// Print the total count below
// Your code here

Hint

Use console.log(countBalls(balls)); to print the result.