[Algorithm] Two Crystal Balls for Square Root Time Complexity
I cannot figure out why my second algorithm doesn't work, yes it is bad and ugly compared to the first one, but still wanna debug it.
The one that works:
The one that doesn't work:
export default function two_crystal_balls(breaks: boolean[]): number {
function getSqrtVal(arr: boolean[]) {
return Math.floor(Math.sqrt(arr.length))
};
let sqrtN = getSqrtVal(breaks); //this is the jump amount but i named the var sqrtN regardless
let brokeIndex = null;
for (let i = 0; i < breaks.length; i += sqrtN) {
const currentValue = breaks[i];
if (currentValue == true) {
brokeIndex = i;
break;
}
};
if (brokeIndex == null) {
return -1;
} else {
// sqrtN = getSqrtVal(breaks);
const safeFloor = brokeIndex - sqrtN;
for (let i = 0; i < sqrtN; i++) {
const currentValue = breaks[safeFloor + i];
if (currentValue == true) {
return (safeFloor + i);
}
};
}
return -1;
export default function two_crystal_balls(breaks: boolean[]): number {
function getSqrtVal(arr: boolean[]) {
return Math.floor(Math.sqrt(arr.length))
};
let sqrtN = getSqrtVal(breaks); //this is the jump amount but i named the var sqrtN regardless
let brokeIndex = null;
for (let i = 0; i < breaks.length; i += sqrtN) {
const currentValue = breaks[i];
if (currentValue == true) {
brokeIndex = i;
break;
}
};
if (brokeIndex == null) {
return -1;
} else {
// sqrtN = getSqrtVal(breaks);
const safeFloor = brokeIndex - sqrtN;
for (let i = 0; i < sqrtN; i++) {
const currentValue = breaks[safeFloor + i];
if (currentValue == true) {
return (safeFloor + i);
}
};
}
return -1;
export default function two_crystal_balls(breaks: boolean[]): number {
function getSqrtVal(arr: boolean[]) {
return Math.floor(Math.sqrt(arr.length))
};
let sqrtN = getSqrtVal(breaks);
let brokeIndex = null;
while (sqrtN < breaks.length) {
const currentValue = breaks[sqrtN];
if (currentValue == true) {
brokeIndex = sqrtN;
break;
}
sqrtN += sqrtN;
};
if (brokeIndex == null) {
return -1;
} else {
sqrtN = getSqrtVal(breaks);
const safeFloor = brokeIndex - sqrtN;
for (let i = 0; i < sqrtN; i++) {
const currentValue = breaks[safeFloor + i];
if (currentValue == true) {
return (safeFloor + i);
}
};
}
return 0;
}
export default function two_crystal_balls(breaks: boolean[]): number {
function getSqrtVal(arr: boolean[]) {
return Math.floor(Math.sqrt(arr.length))
};
let sqrtN = getSqrtVal(breaks);
let brokeIndex = null;
while (sqrtN < breaks.length) {
const currentValue = breaks[sqrtN];
if (currentValue == true) {
brokeIndex = sqrtN;
break;
}
sqrtN += sqrtN;
};
if (brokeIndex == null) {
return -1;
} else {
sqrtN = getSqrtVal(breaks);
const safeFloor = brokeIndex - sqrtN;
for (let i = 0; i < sqrtN; i++) {
const currentValue = breaks[safeFloor + i];
if (currentValue == true) {
return (safeFloor + i);
}
};
}
return 0;
}
1 Reply
Testing file:
import two_crystal_balls from "@code/TwoCrystalBalls";
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);
});
import two_crystal_balls from "@code/TwoCrystalBalls";
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);
});