loading...

Daily Challenge #60 - Find the Missing Letter

thepracticaldev profile image dev.to staff ・1 min read

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!

Posted on by:

thepracticaldev profile

dev.to staff

@thepracticaldev

The hardworking team behind dev.to ❤️

Discussion

markdown guide
 

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)
    }
}

 

Nice, but I think there are a few edge cases you might consider handling:

  • Empty inputs return 0 (I guess that could work).
  • Inputs that don't actually miss a letter will return the ASCII code of the last element.
  • One element inputs return the ASCII code of the only letter (just a special case of the previous point really).

In other words, is returning the character representation of last really a sensible default if the input does not have a missing letter, either due to length or contents?

 

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.

Sure, was just trying to have a discussion. Generally the problems in these challenges are not particularly interesting by themselves, but that doesn't mean one can't turn them into a learning experience by e.g. doing more than what was specified.

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

 

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

 
[deleted]
 

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.

 

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));
};
 

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)
    }
  }
}
 

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

 

F#:

module MissingLetter

let private missingLetter' letters =
    letters
    |> List.pairwise
    |> List.tryFind (fun (a, b) -> (int b) - (int a) > 1)
    |> Option.map (fun (a, _) -> int a + 1 |> char)

let missingLetter (letters : char list) : char option =
    if letters.Length < 2 then None
    else missingLetter' letters

Tests:

module MissingLetterTest

open FsUnit.Xunit
open Xunit
open MissingLetter

[<Fact>]
let ``missing lowercase letter`` () = 
   missingLetter [ 'a'; 'b'; 'c'; 'd'; 'f' ] |> should equal (Some 'e')

[<Fact>]
let ``shortest possible `` () = 
   missingLetter [ 'a'; 'c' ] |> should equal (Some 'b')

[<Fact>]
let ``missing uppercase letter`` () = 
   missingLetter [ 'O'; 'Q'; 'R'; 'S' ] |> should equal (Some 'P')

[<Fact>]
let ``no missing letter`` () =
    missingLetter [ 'a'; 'b'; 'c' ] |> should equal None

[<Fact>]
let ``single element list`` () =
    missingLetter [ 'a' ] |> should equal None
 

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

 

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]
}
 

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++;
    }


}
 

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.

 

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);
  });
};
 

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)
}
 

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)

 

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)
 

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)
 

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!

 

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.

 

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]
  }
}
 

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
 

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