TwoCrystalBalls: Different appraoch

[anwesh-b]

I was thinking if we could solve the Two crystal ball with different appraoch. What if we split the main array into 3 halves and treat the problem similar to binary search, and something like tertiary search.

This will work on time complexity log(n) with base 3 Logic:

Code:

export default function two_crystal_balls(breaks: boolean[]): number {
    let low = 0
    let high = breaks.length;

    do {
        const firstTertile = low + Math.floor((high - low) / 3);
        const secondTertile = low + Math.ceil((high - low) * 2 / 3);

        if (breaks[firstTertile]) {
            high = firstTertile;
        } else if (breaks[secondTertile]) {
            low = firstTertile + 1;
            high = secondTertile;
        } else {
            low = secondTertile + 1;
        }
    } while (low < high)

    return breaks[low] ? low : -1;
}

@ThePrimeagen What is your thought on the appraoch?

[ThePrimeagen]

Unfortunately you haven't really fundamentally changed the running time. If something breaks, you now have to travel, potentially 1/3 of the array.

This is just a form of binary search but instead n-ary search

It is certainly cool, but you will end up having n running time in the end

[anwesh-b]

Can you explain more on what you mean on If something breaks?

[luispellizzon]

I had issue with some arrays with different sizes and I debuged the code and changed only one thing on my algorithm. After the first loops encounters the first TRUE value (where the first ball breaks) the index, according to the GOAT prime, he deducts by the jump amount variable and start from the beginning of that portion again.

What I changed was I incremented index variable because we dont need to check where was the last element before we found the TRUE value, because we know that last element is FALSE, otherwise that last portion of the squared would be checked.

so I did the following: i = i + 1 - jumpAmount

Another solution would be to change the second for loop:

for (let j = 0; j < jumpAmount && i < array.length; ++j, ++i) {
    if (array[i]) {
      return i;
    }
  }

where the loop will run until j variable is less OR equal to jumpAmount.

That happens because depending where the TRUE value is, we are short one element, because the first loop will always check one element more than the amount we want to jump.

const array = [false,false,false,false,false,false,false,false,false,true,true,true,true]

The first run will jump to the 4th element because squared root of 13, rounded down, is 3:

const jumpAmount = 3;
let index = jumpAmount //3
/* First run will check from index 0 to index 3*/
/*If not is found, increment index by 3. Now index = 6*/
/* Second run will check from index 3 to index 6, which will check 4 elements*/

But if we find a TRUE value, which is located in the last index of this portion we are checking, the second loop will only check for 3 elements instead of the whole 4 elements, because the second loop only executes until j variable is less than jump amount. To prevent this we can either increment the start of the index (from the portion we want to check linearly) by 1, because we already know this index is FALSE, or we can still check this last index but we need to make sure that the loop runs until j variable is less or EQUAL to the jump amount variable.