DEV Community

dev.to staff
dev.to staff

Posted on

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:

Alt Text

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 yo+challenge@dev.to with your suggestions!

Top comments (27)

Collapse
 
dak425 profile image
Donald Feury

Time to Go find the missing letter!

missing_letter.go

package find

// MissingLetter indicates what the missing character is in a ordered sequence of characters
func MissingLetter(chars []rune) rune {
    var last int

    for _, r := range chars {
        if last != 0 && int(r)-last > 1 {
            return rune(r - 1)
        }
        last = int(r)
    }

    return rune(last)
}

missing_letter_test.go

package find

import "testing"

type testCase struct {
    description string
    input       []rune
    expected    rune
}

func TestMissingLetter(t *testing.T) {
    testCases := []testCase{
        {
            "two characters",
            []rune{'A', 'C'},
            'B',
        },
        {
            "dev-to example one",
            []rune{'a', 'b', 'c', 'd', 'f'},
            'e',
        },
        {
            "dev-to example two",
            []rune{'O', 'Q', 'R', 'S'},
            'P',
        },
    }

    for _, test := range testCases {
        if result := MissingLetter(test.input); result != test.expected {
            t.Fatalf("FAIL: %s - MissingLetter(%+v): %v - expected %v", test.description, test.input, result, test.expected)
        }
        t.Logf("PASS: %s", test.description)
    }
}

Collapse
 
Sloan, the sloth mascot
Comment deleted
Collapse
 
designfrontier profile image
Daniel Sellers

This makes an assumption about where the missing letter is in the string that isn't valid for all the test cases?

It returns incorrectly for both test cases that they propose in the problem. You're on the right track but have a little bit more work to do.

Collapse
 
cgty_ky profile image
Cagatay Kaya

Thanks for the heads up. I did not get the challenge right and posted a wrong answer. Here is the correct one, I hope :)

missingL = input => {
  const alphabet = [
    "a","b","c","d","e","f","g",
    "h","i","j","k","l","m","n",
    "o","p","q","r","s","t","u",
    "v","w","x","y","z"
  ];

  const alphabetUp = alphabet.map(item => item.toUpperCase());

  input[0] == input[0].toUpperCase()
    ? alphabet.splice(0, 26, ...alphabetUp)
    : alphabet;
  const compareArray = alphabet.slice(
    alphabet.indexOf(input[0]),
    alphabet.indexOf(alphabet[alphabet.indexOf(input[0]) + input.length])
  );

  return compareArray.filter(item => !input.includes(item));
};
Collapse
 
chrisachard profile image
Chris Achard

Here it is in JS, uses charCodeAt and fromCharCode to convert from char to ASCII number, then looks for the number difference of 2 (missing number in between them):

const missing = arr => {
  for(let i in arr) {
    const letter = arr[i]
    const next = arr[Number(i) + 1]
    if(next.charCodeAt(0) - letter.charCodeAt(0) === 2
    ) {
      return String.fromCharCode(arr[i].charCodeAt(0) + 1)
    }
  }
}
Collapse
 
kamaal profile image
Kamaal Aboothalib • Edited

Almost identical but I try with the functional approach and typescript
checks any number of chars instead of one.

const getDiff = (a:number, b: number):number => b - a
const getGap = (a:number, maxDiff:number = 1):number => a - maxDiff
const fillGaps = (a:number, gap:number):string[] => gap > 0 ? [...(Array(gap).fill(0))].map((_, e) => e + 1 )
    .map(i => i + a )
    .map(i => String.fromCharCode(i)) : []

const missing = (input:string[]): string => {
  return input.reduce((a, b, index, array) => {
    const positionIndex = `${b}`.charCodeAt(0)
    const nextPositionIndex:number = index + 1 < array.length ? array[index+1].charCodeAt(0) : positionIndex
    const gap = getGap(getDiff(positionIndex, nextPositionIndex), 1)
    const gaps = fillGaps(positionIndex, gap)
    return [...a,...gaps]
  }, []).join(', ')
}

codesandbox.io/s/quirky-davinci-sk826

Collapse
 
pushkar8723 profile image
Pushkar Anand • Edited

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

Collapse
 
dak425 profile image
Donald Feury • Edited

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.

Collapse
 
peter279k profile image
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++;
    }


}
Collapse
 
willsmart profile image
willsmart

A quicky using reduce in JS

First up it converts the array of letters to an array of char codes.
It then uses reduce to find the 2-code gap, and return the letter with char code one less that that of the letter just after the gap.

If there is more than one gap it will return the letter for the last one.
If there is no 2-code gap, then it will return undefined.

findMissingLetter = letters =>
  letters
    .map(c => c.charCodeAt(0))
    .reduce(
      (acc, code, index, codes) => (index && code == codes[index - 1] + 2 ? String.fromCharCode(code - 1) : acc),
      undefined
    );

(checked on kata)

Collapse
 
rafaacioly profile image
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)
Collapse
 
colorfusion profile image
Melvin Yeo • Edited

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)
Collapse
 
designfrontier profile image
Daniel Sellers • Edited

Here is another JS version

const LETTERS = [
  'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 
  'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 
  'x', 'y', 'z'
];

const findMissing = ltrArr => {
  const offset = LETTERS.findIndex(l => l === ltrArr[0].toLowerCase());
  const index = ltrArr.findIndex((l, i) => l.toLowerCase() !== LETTERS[offset + i]);

  return ltrArr[0].toLowerCase() === ltrArr[0]
    ? LETTERS[index + offset]
    : LETTERS[index + offset].toUpperCase();
};

The LETTERS constant could be inside the findMissing function... but that seemed less reusable. Covers all the test cases and should only iterate the arrays fully if there is no missing character to be found. So should be pretty fast as well.

Collapse
 
marcoslooten profile image
Marco Slooten

Nice challenge, I tried doing it in JS with an array.reduce and character codes. I think it works well enough! I don't think the arr.splice(1) is really clean though, so perhaps a traditional loop would be better.

const returnMissingLetter = letters => {
  return letters.reduce((acc, curr, i, arr) => {
    if (curr.charCodeAt() - acc.charCodeAt() === 1) {
      return curr;
    }
    arr.splice(1);
    return String.fromCharCode(acc.charCodeAt() + 1);
  });
};
Collapse
 
vjoao profile image
Victor Nascimento • Edited

const hasLargerDiff = (num, index, list) => list[index + 1] - num > 1;
const toCharCode = char => char.charCodeAt(0);

function findMissingLetter(sequence) {
  const missingCode = sequence
    .map(toCharCode)
    .find(hasLargerDiff) + 1;

  return String.fromCharCode(missingCode)
}
Collapse
 
rdelga80 profile image
Ricardo Delgado • Edited

This my solution, I also tried to account for the possibility that there wasn't just one letter missing:

checkChar = array => {
    const missing = []

    for(let i = 1; i < array.length; i++) {
        var firstLet = array[i].charCodeAt(0)
        var prevLet = array[i - 1].charCodeAt(0)
        if (firstLet - prevLet > 1) missing.push([firstLet, prevLet])
    }

    return missing.map(letterArray => {
        const letters = []

        for(let i = letterArray[1] + 1, c = 0; c < (letterArray[0] - letterArray[1] - 1); c++) {
            letters.push(String.fromCharCode(i))
            i++
        }
        return letters
    })[0]
}
Collapse
 
aminnairi profile image
Amin • Edited

My take at the challenge written in TypeScript this time and using a recursive solution!

"use strict";

type Letters = string[];
type LetterCode = number | undefined;
type MissingLetter = string | false;

function missingLetter(
    letters: Letters,
    nextLetterCode: LetterCode = undefined
): MissingLetter {
    if (letters.length === 0) {
        return false;
    }

    if (nextLetterCode === undefined) {
        nextLetterCode = letters[0].charCodeAt(0);
    }

    const [ letter, ...rest ]: Letters = letters;
    const letterCode: LetterCode = letter.charCodeAt(0);

    if (letterCode !== nextLetterCode) {
        return String.fromCharCode(letterCode - 1);
    }

    return missingLetter(rest, nextLetterCode + 1);
}

console.log(missingLetter(["a", "b", "c", "d", "f"])); // "e"
console.log(missingLetter(["O", "Q", "R", "S"])); // "P"
console.log(missingLetter(["a", "b", "c", "d", "e", "f"])); // false

I haven't done that much of a test so do not hesitate to tell me if I'm wrong. I also have returned false whether when there was no missing letters. I guess my solution will fail when the first letter is at the beginning or at the end of the array. The source-code with the playground is available here!

Collapse
 
aminnairi profile image
Amin • Edited

I also did use my algorithm in Elm. Here is the source-code for the inner logic function.

getMissingLetter : List Char -> Char -> Maybe Char
getMissingLetter letters nextCharacter =
    case letters of
        [] ->
            Nothing

        letter :: rest ->
            let
                characterCode =
                    Char.toCode letter

                nextCharacterCode =
                    Char.toCode nextCharacter
            in
            if characterCode /= nextCharacterCode then
                Just nextCharacter

            else
                getMissingLetter rest <| Char.fromCode <| nextCharacterCode + 1

I bet there could be a way to use it in Haskell or PureScript as well, but I'm more confortable using Elm for now.

And the testing is of course available here on Ellie App.

Collapse
 
cvanpoelje profile image
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]
  }
}