Created
June 2, 2022 01:02
-
-
Save ApprenticeGC/7f10faed9bf44287f53ffa370af539f1 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Utility functions | |
function populateNumbers(startNum, endNum, missingNum) { | |
let numbers = []; | |
for (let i = startNum; i <= endNum; ++i) { | |
if (i !== missingNum) { | |
numbers.push(i) | |
} | |
} | |
return numbers; | |
} | |
function showNumbers(numbers) { | |
let indexDesc = ""; | |
for (let i = 0; i < numbers.length; ++i) { | |
indexDesc = `${indexDesc}, ${i}`; | |
} | |
indexDesc = indexDesc.substring(2); | |
let desc = ""; | |
for (let i = 0; i < numbers.length; ++i) { | |
desc = `${desc}, ${numbers[i]}`; | |
} | |
desc = desc.substring(2); | |
console.log(`\n${indexDesc}\n${desc}\n`); | |
} | |
// Actual function(s) to show missing number | |
function showMissingNumber(level, numbers) { | |
const count = numbers.length; | |
if (count == 2) { | |
console.log(`the last two numbers: ${numbers[0]}, ${numbers[1]}`); | |
const missingNumber = numbers[0] + 1; | |
console.log(`found at ${level + 1} step(s), missingNumber is ${missingNumber}`); | |
return; | |
} | |
const middleIndex = Math.floor((count - 1) / 2); | |
const numberAtMiddleIndex = numbers[middleIndex]; | |
const firstNumber = numbers[0]; | |
const lastNumber = numbers[count - 1]; | |
const halfLastNumber = Math.floor((lastNumber + firstNumber - 1) / 2); | |
const desc = `count: ${count} middleIndex: ${middleIndex} numberAtMiddleIndex: ${numberAtMiddleIndex} lastNumber: ${lastNumber} halfLastNumber: ${halfLastNumber} `; | |
console.log(desc); | |
let subNumbers = []; | |
if (halfLastNumber >= numberAtMiddleIndex) { | |
subNumbers = numbers.slice(middleIndex, count); | |
console.log(`missing number at right half`); | |
} else if (halfLastNumber < numberAtMiddleIndex) { | |
subNumbers = numbers.slice(0, middleIndex + 1); | |
console.log(`missing number at left half`); | |
} | |
// showNumbers(subNumbers); | |
showMissingNumber(level + 1, subNumbers); | |
} | |
// showMissingNumber(0, numList001); | |
// showMissingNumber(0, numList002); | |
const numList001 = populateNumbers(1, 9, 6); | |
const numList002 = populateNumbers(1, 15, 8); | |
const numList003 = populateNumbers(1, 5678901, 3); | |
showNumbers(numList001); | |
showMissingNumber(0, numList001); | |
showNumbers(numList002); | |
showMissingNumber(0, numList002); | |
// showNumbers(numList003); | |
showMissingNumber(0, numList003); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Using binary partition scheme to find one and the only missing number from sorted, ascending order numbers. And the missing numbers will be in any where except the first and the last position.