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 yo+challenge@dev.to with your suggestions!
Top comments (23)
Time to Go find the missing letter!
missing_letter.go
missing_letter_test.go
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 :)
Here it is in JS, uses
charCodeAt
andfromCharCode
to convert from char to ASCII number, then looks for the number difference of2
(missing number in between them):Almost identical but I try with the functional approach and typescript
checks any number of chars instead of one.
codesandbox.io/s/quirky-davinci-sk826
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:
Try / Fork it ideone.com/YXz3HL
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.
Here is PHP solution with
chr
andord
functions:A quicky using
reduce
in JSFirst 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.
(checked on kata)
Python solution :)
I wrote the code (in Python) assuming that the missing letter is within the list, if not there would be 2 answers to it.
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 🤣)
Here is another JS version
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.