educative.io

Educative

An alternate solution to missing number

/**
*

  • @param input input to find missing value in between 0 & n in array size of 1 less
  • returns zerothIndex
    */
    const findMissingNumber = (input: Array): number => {
    const length = input.length;
    const ZERO = 0;
    let index = 0;
    let zerothIndex = 0
    while (index < length) {
    const currentVal = input[index];
    if (currentVal === ZERO) {
    zerothIndex = index;
    index += 1;
    continue;
    // skip the rest?
    }
    const jIndex = currentVal - 1;
    if (jIndex !== index) {
    // swap till things are in place
    [input[jIndex], input[index]] = [input[index], input[jIndex]]
    } else {
    // nothing to swap, move on
    index += 1;
    }
    }
    console.log(‘kinda sorted value is, zerothIndex’, {
    input, zerothIndex
    });
    const missingNumber = zerothIndex + 1;
    return missingNumber;
    }

Good, only one loop! I found something similar:

def find_missing_number(nums):
  i = 0
  missing = len(nums)
  while i < len(nums):
    if nums[i] == len(nums):
      missing = i
      i += 1
    elif nums[i] != i:
      j = nums[i]
      nums[i], nums[j] = nums[j], nums[i]
    else:
      i += 1
  return missing