526互联

[Algorithm] Two crystal balls problem

发布时间 2023-07-08 20:26:45作者: Zhentiw

You're given two identical crystal balls and a 100-story building. The balls are incredibly tough, but there exists some floor in the building, above which the balls will break when dropped, and below which they will not. You don't know what this floor is, but you want to find out with the fewest possible drops. How do you do it?

 

/**
 * Noramlly we would consider find middle point of the array
 * But if assume the first ball break, then we need to walk through
 * half of the array to find the breaking point.
 *
 * There fore the T: O(N/2) = O(N).
 *
 * We want better than that.
 *
 * So what we can do is we take step of sqrt(N) each time for the first ball
 * If it breaks, then we can walk through the sqrt(N) array to find the breaking point.
 *
 * O(sqrt(N)) < O(N)
 */
export default function two_crystal_balls(breaks: boolean[]): number {

    const jumpAmount = Math.floor(Math.sqrt(breaks.length))

    // using first ball to find the breaking point range
    let i = 0
    while (jumpAmount * i < breaks.length) {
        if (breaks[jumpAmount * i]) {
            break
        }
        i++
    }

    // using second ball to find actual breaking point
    let j = jumpAmount * (i - 1)
    for (let k =0; k < jumpAmount; k++) {
        if (breaks[j + k]) {
            return j + k
        }
    }

    return -1
}

 

Test:

test("two crystal balls", function () {
    let idx = Math.floor(Math.random() * 10000);
    const data = new Array(10000).fill(false);

    for (let i = idx; i < 10000; ++i) {
        data[i] = true;
    }

    expect(two_crystal_balls(data)).toEqual(idx);
    expect(two_crystal_balls(new Array(821).fill(false))).toEqual(-1);
});