Daily Challenge #60 - Find the Missing Letter

Write a method that takes an array of consecutive (increasing) letters as input and that returns the missing letter in the array.

You will always get a valid array. And it will be always exactly one letter be missing. The length of the array will always be at least 2.
The array will always contain letters in only one case.

Example:

Good luck!

---

Today's challenge comes from user5036852 onCodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email [e-mail] with your suggestions!

Comments

[Mat-R-Such]

Python

def missingLetter(chain):
    for i in range(1,len(chain)):
        if chr(ord(chain[0])+i) != a[i]:
            print(chr(ord(chain[0])+i))
            break

[peter279k]

Here is PHP solution with chr and ord functions:

function find_missing_letter(array $array): string {
    $start = ord($array[0]);

    foreach($array as $char) {
        if ($char !== chr($start)) {
            return chr($start);
        }

        $start++;
    }


}

[Rafael Acioly]

Python solution :)

from typing import List


def missing_letter(letters: List[str]) -> str:
  number_rep = [ord(letter) for letter in letters]
  letters_range = range(number_rep[0], number_rep[-1])
  original_set = set(number_rep)

  missing = sorted(set(letters_range) - original_set).pop()
  return chr(missing)

[Arihant Godha]

Will this always be sequential? Like mentioned in the example?

[cvanpoelje]

My solution in Javascript

const missing = arr => {
  const alphabet = "abcdefghijklmnopqrstuvwxyz".split("");
  arr = arr.map(item => item.toLowerCase());
  for (let i in arr) {
    if (!arr.includes(alphabet[alphabet.indexOf(arr[i]) + 1]))
      return alphabet[alphabet.indexOf(arr[i]) + 1]
  }
}

[Donald Feury]

Oh no of course, you are right and I agree with all the points you made.

[Donald Feury]

Meaning, slice is always valid, always has length of at least 2, always has exactly one character missing, and all the characters will be of the same case.

My solution includes no consideration for these edge cases since within the context of this challenge, those edge cases don't exist.

[Donald Feury]

Its not but I didn't really have much time for this at the time. So I implemented it within the context of the challenge as specified

[Pushkar Anand]

I really like this question. Though the naive solution would be to just iterate through the array and print the missing letter. Resulting in O(n) complexity. We can modify the binary search algorithm to reduce the complexity to O(logn).

The logic is simple. Just split the array into two equal parts and find the difference of ASCII code of char at the start and end of each part. The part where the difference is greater, is the one where the missing letter lies. Now recursively call the same function on the part where the missing letter lies.
The base condition would be an array with length 2. In this case, the missing letter is just after the first char.

However, there are a few edge cases to consider.
1. What will be our mid in case of array with odd length?
Well, it is easy, include the mid element in both array.
mid = arr.length/2

2. What will be our mid in case of array with even length?
We need to split our array into two equal halves, otherwise, the one with smaller length might have the missing letter. In which case both the difference will be equal. So, to solve this, we will have 2 mids.
mid1 = (arr.length - 1) / 2
mid2 = arr.length / 2
This is also convenient as in case of odd length, mid1 will be equal to mid2.
For example, let's consider an array of length 5.
mid1 = (5 - 1) / 2 = 2
mid1 = 5 / 2 = 2 (integer division)
So, we don't need to introduce a branch in our code for this! 🎉

3. What if the missing number is exactly in the center?
Well, in this case, the difference between both parts will be equal. We need to handle this as a special case.

4. What if splits results in an array with length less than 2?
This will only happen when an array of length 3 was divided into two parts and the missing letter is just after the first letter. For this, we just need to adjust our base condition. We change it from 2 to <= 2. Again not introducing a branch in our code.

Final code:

function findMissingLetter(arr) {
    // Base condition
    // When array length is less than 2 then the second letter is missing.
    if (arr.length <= 2) {
        return String.fromCharCode(arr[0].charCodeAt(0) + 1);
    }

    const midPos1 = Math.floor((arr.length-1)/2);
    const midPos2 = Math.floor(arr.length/2);
    const start = arr[0].charCodeAt(0);
    const mid1 = arr[midPos1].charCodeAt(0);
    const mid2 = arr[midPos2].charCodeAt(0);
    const end = arr[arr.length - 1].charCodeAt(0);

    if (mid1 - start > end - mid2) {
        return findMissingLetter(arr.slice(0, midPos1));
    } else if (mid1 - start < end - mid2) {
        return findMissingLetter(arr.slice(midPos2));
    } else {
        // If both split are equal then the letter missing is at the center.
        return String.fromCharCode(mid1 + 1);
    }
}

Try / Fork it ideone.com/YXz3HL

[Melvin Yeo]

I wrote the code (in Python) assuming that the missing letter is within the list, if not there would be 2 answers to it.

def missing_letter(input):
    for index in range(len(input) - 1):
        if ord(input[index + 1]) - ord(input[index]) != 1:
            return chr(ord(input[index]) + 1)

Here is my previous implementation, I wrote this to handle the scenario that the input list wasn't in an ascending order (I didn't read the question completely 🤣)

def missing_letter(input):
    arr = [input[0]] + [None] * len(input)

    for elem in input[1:]:
        if elem < arr[0]:
            offset = elem - arr[0]
            arr = arr[offset::] + arr[:offset]
            arr[0] = elem
        else:
            arr[ord(elem) - ord(arr[0])] = elem

    for index, elem in enumerate(arr):
        if elem is None:
            return chr(ord(arr[0]) + index)