Find The Lucky Number In An Array

Intro

For this algorithm, we are given an array of integers and are tasked with returning a "lucky number". In this case, a lucky number is an integer that has a frequency in the array equal to it's value. For example, let's say we have have the following array: [1, 2, 3, 8, 2, 4]. The lucky number for this array would be 2, because it's value is 2, and it also appears two times in the array.

If we have several lucky numbers, we should return the one with the greatest value. For example, in the array [1, 2, 6, 4, 2, 4, 5, 4, 7, 4], we would return the number 4, as its value is 4 and it appears four times in the array. Even though 2 is a lucky number in the array as well, it is less than 4, so we disregard it.

The final case we need to support is if there are no lucky numbers in the array. In that case, we should just return -1.

Getting Started

Let's get started by setting up our function. It will accept an array as an argument, and return a number.

/**
 * @param {number[]} nums
 * @return {number}
 */
const findLuckyNumber = (nums) => {
  // do stuff here.
}

Now that we're all set up, where do we go from here? Well, anytime you're faced with counting the number of occurrences of something, you should think of using an object. We can loop through the nums array and tally the occurrences in this object.

/**
 * @param {number[]} nums
 * @return {number}
 */
const findLuckyNumber = (nums) => {
  const counts = {}

  for(const num of nums) {
    counts[num] = counts[num] + 1 || 1
  }
}

If you wanted to get fancy, you could instead use the Array.reduce method instead.

/**
 * @param {number[]} nums
 * @return {number}
 */
const findLuckyNumber = (nums) => {
  const counts = arr.reduce((acc, num) => (
      { ...acc, [num]: acc[num] + 1 || 1 }
  ), {})
}

Going forward I will show you code snippets for both easy and fancy versions. Sometimes it's best to write easy to read code versus trying to show off. However, if you are working with more experienced developers, the fancy version should be simple to understand.

For the remainder of this article, let's pretend that we are working with the following array: [1, 5, 2, 5, 4, 3, 5, 7, 5, 3, 3, 5]. The number 5 will end up being our lucky number. After executing the code above, counts should result in an object that looks the this:

{
  '1': 1,
  '2': 1,
  '4': 1,
  '3': 3,
  '5': 5,
  '7:' 1
}

From here we need to loop through this counts object somehow, and eliminate any numbers that do not have the same frequency as it's value. We can do so be using a for in loop for our easy version.

/**
 * @param {number[]} nums
 * @return {number}
 */
const findLuckyNumber = (nums) => {
  const counts = {}

  for(const num of nums) {
    counts[num] = counts[num] + 1 || 1
  }

  const frequencies = []

  for(const key in counts) {
      if(parseInt(key) === counts[key]) {
          frequencies.push(counts[key])
      }
  }
}

For you fancier people, you could use the Object.entries method.

/**
 * @param {number[]} nums
 * @return {number}
 */
const findLuckyNumber = (nums) => {
  const counts = arr.reduce((acc, num) => (
      { ...acc, [num]: acc[num] + 1 || 1 }
  ), {})

  const frequencies = Object.entries(counts).filter(entry => (
    parseInt(entry.key) === entry.value
  )).map(entry => entry[1])
}

Now all that we need to do is add one more line of code, and we are done. This line of code will check to see if the frequencies array is empty. If it is, return -1. Otherwise, return the number that is at the end of the array, since it is already sorted.

return frequencies.length === 0 ? -1 : frequencies[frequencies.length - 1]

Final Versions

Here is the final code for this algorithm. First the beginner friendly version, then the fancier one.

/**
 * @param {number[]} nums
 * @return {number}
 */
const findLuckyNumber = (nums) => {
  const counts = {}

  for(const num of nums) {
    counts[num] = counts[num] + 1 || 1
  }

  const frequencies = []

  for(const key in counts) {
      if(parseInt(key) === counts[key]) {
          frequencies.push(counts[key])
      }
  }

  return frequencies.length === 0 ? -1 : frequencies[frequencies.length - 1]
}

A fancier version:

/**
 * @param {number[]} nums
 * @return {number}
 */
const findLuckyNumber = (nums) => {
  const counts = nums.reduce((acc, num) => (
      { ...acc, [num]: acc[num] + 1 || 1 }
  ), {})

  const frequencies = Object.entries(counts).filter(entry => (
    parseInt(entry.key) === entry.value
  )).map(entry => entry[1])

  return frequencies.length === 0 ? -1 : frequencies[frequencies.length - 1]
}

If you have any problems understanding any of this, feel free to shoot me a message, and I'll make sure it's crystal clear.