Binary Search on Answer Technique in DSA Typescript - Build from Scratch

Binary Search on Answer Technique

📖 Scenario: Imagine you are organizing a party and want to divide candies equally among children. You have a list of candy packs with different counts. You want to find the maximum number of candies each child can get so that all children get the same amount and no candy is wasted.

🎯 Goal: Build a program that uses the Binary Search on Answer Technique to find the maximum number of candies each child can get equally from the given candy packs.

📋 What You'll Learn

Create an array called candyPacks with the exact values: [10, 15, 20, 17]

Create a variable called children and set it to 5

Write a function called canDistribute that takes a number candies and returns true if it is possible to give each child candies candies from the packs, otherwise false

Use binary search between 1 and the maximum candies in any pack to find the maximum candies per child

Print the maximum candies each child can get

💡 Why This Matters

🌍 Real World

This technique helps in resource allocation problems like dividing goods, bandwidth, or tasks evenly.

💼 Career

Binary search on answer is a common pattern in coding interviews and competitive programming to optimize search over a range of answers.

1

Create the candy packs array

Create an array called candyPacks with these exact values: [10, 15, 20, 17]

DSA Typescript

# Your code here

Hint

Use const candyPacks: number[] = [10, 15, 20, 17]; to create the array.

2

Set the number of children

Create a variable called children and set it to 5

DSA Typescript

const candyPacks: number[] = [10, 15, 20, 17];
# Your code here

Hint

Use const children: number = 5; to set the number of children.

3

Write the function to check distribution possibility

Write a function called canDistribute that takes a number candies and returns true if it is possible to give each child candies candies from the packs, otherwise false. Use a for loop to sum how many children can be served with candies from each pack.

DSA Typescript

const candyPacks: number[] = [10, 15, 20, 17];
const children: number = 5;

# Your code here

Hint

Count how many children can get candies by dividing each pack by candies and summing. Return true if count is at least children.

4

Use binary search to find maximum candies per child and print result

Use binary search between 1 and the maximum number in candyPacks to find the maximum candies each child can get. Print the result using console.log(maxCandies).

DSA Typescript

const candyPacks: number[] = [10, 15, 20, 17];
const children: number = 5;

function canDistribute(candies: number): boolean {
    let count = 0;
    for (let pack of candyPacks) {
        count += Math.floor(pack / candies);
    }
    return count >= children;
}

# Your code here

Hint

Use binary search to test mid values. If canDistribute(mid) is true, move left up and update maxCandies. Otherwise, move right down. Print maxCandies at the end.