2023-06-23

 23 Jun 2023

Generate a Random Number that isn't in a List of Integers

Taken from DailyCodingProblem

Given an integer n and a list of integers l, write a function that randomly generates a number from 0 to n-1 that isn’t in l (uniform).

Solution

This is the answer I came up with:

function uniformRandom(integer: number, list: Array<number>): number {
  // Generate the range of number from zero to n - 1
  let integerRange = []
  for (let _ = 0; _ < integer; _++) {
    integerRange.push(_)
    }

  // Find the symmetric difference between integerRange and list
  let integerRangeSet = new Set(integerRange)
  let listSet = new Set(list)
  let safeRangeSet = new Set(integerRange)
  for (let element of listSet) {
    if (integerRangeSet.has(element)) {
      safeRangeSet.delete(element)
    }
  }
  // Create a safe array containing the difference
  let safeRange = Array.from(safeRangeSet)

  // Find a random array index within the safe array
  let randomIndex = Math.floor(Math.random() * safeRange.length)

  return safeRange[randomIndex]
}

Testing

Solution tested in REPL:

https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABOGw4CcC2AlAhmAEzkwAoYwoBTAc0vQC5EwRMAjOgGkQBsYBnKIwCC6dLgCeAHmZs6APgCUjGe3SIA3gFgAUIkQB6fYgDilMHVxVEUABaVEYsLURxgTFqsTB0xRAC86OGsgpABaRABGHT1uSihEcipadDwnewBeRABtAF1orwxEElj4gH1ETIAGAG5EcskEiho6WtKAajaFDXy9ROaU-FoAOgAHED4bElKFHsQAXx18w0QAMXICaztEPnFMTDj0GAhEAlRgOjMIe3YoAHdKM0akulTnfA3eAXySp-7XygAynEKkxKLdEECoGQmsl-jNdDxgZ8oJCQeZwZDivwoPCYsC+Lhzv9UZl0RC4tDngM0riCmpisDKLF9hQXG5kZCuloEb03JS-oNAXEhjZcHwSEzKCycVzZnoCUTBZChgRJVQJcyzDjZgsEbq9MsAMLoSiWey4baE82iCSICAIKC4cjkaibeynYDnE2QSjffFW-4gkRicRDbzEEgKyjEuLwpZGNaERAWxxETDJm3iRqqgAeiFuMFs5DdlvOGZDfviqeIAElCJQ85kALKWGxh7hwDAkFu2IbV0hdABUpejgqGsSctjjCJNUBA6CQUf+WX7ddzeW0up0PyQmQATJVt0iQVkIlw91wAMxcAAsXAArFwAGxcACcXAi18iAA4Nzp7WAfBwLE45wNQJD5CgaBYKkaYkGAXDcF0yxCGAWaStKXg+OmWSVFwADsXDfh+eGRGekQXpEd6RI+kQvpEhGRK+G7Tj8pS7pEh7aGx3AnqR5GUV+9GMb+izaABQEgR24GQWAqAYDg7wRuxXClEhBhGKh6Gaqy4Y4dRtHMTorHAqU7EghEXFsWpfEfueV63s+BFER+lGfn+4kIJJlCgTJCJQQpsHKSpdRqchmloYgGFalhvhZIZLE6EAA

Copyright © Paramdeo Singh · All Rights Reserved · Built with Jekyll

This node last updated November 7, 2023 and is permanently morphing...

Paramdeo Singh Guyana

Generalist. Edgerunner. Riding the wave of consciousness in this treacherous mortal sea.

Technology Design Strategy Literature Personal Blogs
Search Site

Results are from Blog, Link Dumps, and #99Problems