[Challenge] Find the Missing Number 🔎

challenge

#1

Code Challenge #22: September 6, 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer’s job interview at places such as Google and Facebook.

This week’s challenge was reported to have been asked in interviews at Twitter:


Basic Difficulty

You have a bag containing tiles with numbers [1, 2, 3, …, 100] written on them. Each number appears exactly once, so there are 100 tiles and 100 numbers. Now, without looking, one number tile is randomly picked out of the bag and discarded. Write a function, missingNo, that will find the missing number.

  • Function Name: missingNO
  • Input: an array, [1, 2, …, 100] with one number between 1 and 100 missing.
  • Output: an integer, the “missing” number in the array
  • Example: missingNo([1, 3, …, 100]) => 2 if the array was missing the number 2. Please include in your submission a test array with number 66 missing.
  • The array may not be sorted.
  • The removal of a number from the bag is totally random, there is no way to tell what number it was by the process of removing it (e.g. you cannot feel what number is written on the tile)
  • You may look in the bag of number tiles and interact with the contents once the random number is removed. So, you can lay all of the tiles out,
  • Always remember to explain your code and the thought processes behind it!
  • What if your interviewer had follow-up questions or extensions to this challenge? Don’t anticipate what exactly those follow-ups or changes may be, but try to write your code so that it is easily read, easily maintained, and can be adapted to potential modifications in the interviewer’s questioning.
Find out more about basic challenges.

Intermediate difficulty

You replace the missing number in the bag, so you again have 100 tiles numbered from 1 to 100. This time, you remove two random number tiles. Write a function, missingNOs, that will find the missing numbers.

  • Function Name: missingNOs
  • Input: an array, [1, 2, …, 100] with two numbers between 1 and 100 missing.
  • Output: an array of two integers, showing both “missing” numbers in the array in any order
  • Example: missingNOs([1,4, …, 100) => [2, 3]
  • Do you have to write a second script (i.e. write another version of missingNO to solve this challenge, or could you simply generalize what you’ve made in the basic challenge?
  • You must explain your submission to be able to win!
Find out more about intermediate challenges.

Hard Difficulty

Write a function, missingNoKetsuban, that will efficiently solve for a bag of size n (array elements in range from 1 to n) exactly k numbers missing from the bag.

  • You could think of this as a generalization of what you’d learn by solving the basic and intermediate level challenges.
  • Don’t forget to explain your submission just as you would do in a job interview setting!

Find out more about hard challenges and Big O

Reply to this thread with a link to your code on repl.it and paste your properly formatted code to participate! Don’t just submit your code, remember to explain your solution, too! If you want to be considered as the winner, your function must have the correct name and provide output in the format specified above, you also need to abide by our other simple rules.

As always solutions using imports to do all the heavy lifting such as itertools will not be considered for the winner.

When including your repl.it link, please just give us the link and not the code preview! Just put a space before your URL so that the preview box doesn’t show – too many preview boxes can make the thread hard to read.


The fine print:

Click the links to find out more about:


#3

Python 3.6 -

Basic / Intermediate / Hard Challenge -

Look for the explanation in the comments.
Here I have assumed that input array will only have integers greater than 0 and no repetition of numbers.
The program can be easily modified to deal with different situations where error occurs.

def missingNO(inputArray):
    notFounds = missingNoKetsuban(inputArray, 100)
    if len(notFounds) != 1:
    # Since this function only finds one missing integer from an array, raise error if more than 1 or no missing found
        raise ValueError('More than one number or None missing!')
    else:
        return next(iter(notFounds))

def missingNOs(inputArray):
    return missingNoKetsuban(inputArray, 100)

def missingNoKetsuban(inputArray, n=None):      # Worst case O(2*N) i.e. O(N)
    N = max(inputArray) if n is None else n     # O(1) if n is default else O(N) to find max int in the array
    notFounds = set([x for x in range(1, N+1)]) # O(N)
    # notFounds is set of all the integers from 1 to N
    # I have used set here instead of other arrays cause its operations are fastest
    # for example, time complexity of retrieving, removing, looking an element in set is O(1)
    # Now convert the input array into set for next operation
    # get the difference between the two sets, only has those elements are left which are missing from input array
    return notFounds-set(inputArray)            # O(len(notFounds)) i.e. O(N)

Output : 
# if 2 missing
missingNo([1, 3, …, 100]) => 2
# if 2, 3 missing
missingNOs([1,4, …, 100) => {2, 3}
# if 249, 527, 701, 783, 873 missing
missingNoKetsuban([1,2,3, …, 1000) => {249, 527, 701, 783, 873}

https://repl.it/KkWU/1

Edit :
I found that creating set from list of numbers from 1 to N is unnecessary, the list itself is good enough.
Here I check if numbers from 1 to n are in input array or not, which has constant time complexity O(1) as I converted input array to set whereas checking an element’s presence in list is time costly with time complexity O(n). Thus total time complexity is linear as my above solution(and not really any big difference) but reduced little time by not converting list to set.

def missingNoKetsuban(inputArray, k=None):       # O(n), where n is total number of integers in array including those are missing and length of input array is n-k
    N = max(inputArray) if k is None else len(inputArray)+k     # O(1) if k is passed as argument else O(n-k) to find max int in the array which decides the length n
    notFounds = []                               # O(1)
    # notFounds is empty list, which will contain all missing numbers
    # Now convert the input array into set for next operation
    arraySet = set(inputArray)                   # O(n-k)
    # I have used set here instead of other arrays cause its operations are fastest
    # for example, time complexity of retrieving, removing, looking ANY element in the set is O(1)
    for each in range(1, N+1):                   # O(n)
        if not(each in arraySet):                # O(1)
            # append only those elements to notFounds which are missing from input array
            notFounds.append(each)               # O(1)
    return notFounds

https://repl.it/KkWU/5


#4

Here is my submission in Python 3 for all difficulties:

from random import randint

u = set()
for v in range(30):
    u.add(randint(1,25))

s = set()
s.add(1)
s.update(x for x in range(4, 101))

t = set(x for x in range(1, 66))
t.update(x for x in range(67, 101))

def missingNoKetsuban(n,b):
    a = set(x for x in range(1, n+1))
    c = set(b)
    return list(a-c)
    
def missingNOs(b):
    return missingNoKetsuban(100,b)

def missingNO(b):
    return missingNoKetsuban(100,b)[0]

bag1 = list(t)
print(missingNO(bag1))
bag2 = list(s)
print(missingNOs(bag2))
bag3 = list(u)
print(missingNoKetsuban(25,bag3))

Here is the corresponding output:

66
[2, 3]
[5, 7, 8, 15, 24]

n.b. due to the randomization in the last test case, each run may differ.

And the link:
https://repl.it/Kjab/23

I decided to create a set of all the possible tiles
and compare that with a set generated from
the “bag” array parameter as a list.
This set difference is convert back into an array list return value.
I was able to “reuse” code from the general case
of missingNoKetsuban, in the more specific cases
of missingNO and missingNOs.


#5

Here’s a Java solution for Hard difficulty.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

public class Main {
    
    public static void main(String[] args) {
        
        // Size of the bag
        int n = 100;
        // lost elements
        int k = 10;
        
        Random rand = new Random();
        ArrayList<Integer> randList = new ArrayList();
        int r;
        while (randList.size() != k) {
            r = rand.nextInt(n) + 1;
            if (!randList.contains(r)) {
                randList.add(r);
            }
        }
        int[] array = new int[n-k];
        int i = 0;
        int count = 1;
        while (i != array.length) {
            if (randList.contains(i + count)) {
                count ++;
            } else {
                array[i] = i + count;
                i ++;
            }
        }
        System.out.println("ArrayList of random tiles taken out \n" + randList + "\n");
        System.out.println("The tiles in the bag \n" + Arrays.toString(array) + "\n");
        System.out.println("Output from missingNo method \n" + missingNo(array, n));
    }
    
    public static ArrayList<Integer> missingNo(int[] array, int n) {
        int i = 0;
        int shouldBe = 1;
        ArrayList<Integer> missings = new ArrayList();
        while (array.length + missings.size() != n) {
            if (i >= array.length || shouldBe != array[i]) {
                missings.add(shouldBe);
                shouldBe ++;
            } else {
                i ++;
                shouldBe ++;
            }
        }
        return missings;
    }
}

I create an ArrayList for the amount of tiles that should be removed and generate random distinct intergers until I have the wanted amount (k).

I create an array of size n-k (the size of the bag - the amount of tiles you remove from it) to simulate the bag missing pieces. I iterate through it to add the values and skip the ones that are in the Arraylist of random tiles.

Then I call misingNo with the array I just made as input (the bag with the missing tiles).

Since the values are sorted in the array, I just iterate through the array and compare every value to the value that it should be, represented by an int ’ shouldBe’ that increments from 1 until I have all the missing values. When a value is missing I increment ‘shouldBe’ to simulate the skip and store it in the output arraylist of missing tiles.

Return the arraylist of missing tiles and print.

Regarding imports, Arrays is just for print purposes.

https://repl.it/Kkcq/2


#6

My solution for the basic and hard difficulties using Python: https://repl.it/Kkwj/2

# For the basic difficulty, I created a function that takes a list in the range from 1 to 100 (bag) as the argument and removes the number 66 from that list.
# While, for the hard difficulty, the arguments of my function are n (the total number of tiles) and k (the number of removed tiles).
# The missingNoKetsuban function chooses k random number tiles through the random.randint() function and discards them from the array in the range from 1 to n using a for-loop.
# Then, for both functions, I considered all the remaining number tiles, laid them out in the corresponding empty lists I created at the beginning and looked for the missing number tile (with a for-loop for the basic difficulty and with a list comprehension for the hard difficulty).

import numpy as np
import numpy.random as rand

table = []
table_1 =[]

def missingNO(bag):
    bag.remove(66)
    for el in bag:
        table.append(el)
    for x in range(1,101):
        if x not in table:
            return x

def missingNoKetsuban(n,k):
    bag = list(range(1,n))
    rand_numbs = rand.randint(1,n,k)
    for i in rand_numbs:
        bag.remove(i)
    for el in bag:
        table_1.append(el)
    miss_numb = [x for x in range(1,n) if x not in table_1]
    return miss_numb

print(table, '--->', missingNO(list(range(1,101))))
print(table_1, '--->', missingNoKetsuban(21,3))

#7

Intermediate and Hard Level in Python

def missingNoKetsuban(inp):
    res = []
    inp.append(0)
    hist = dict()
    for number in inp:
        dec = number//10
        hist[dec] = hist.get(dec,[]) + [number]
    for key,value in hist.iteritems():
        if len(value)==10:
            continue
        elif key==(len(hist)-1):
            value.sort()
            twin = range(key*10, (value[-1]+1))
        else:
            twin = range((key*10),((key+1)*10))
        diff = [item for item in twin if item not in value]
        res = res + diff
    return res
            
ar = range(1,101)
ar.remove(66)
ar2 = range(1,101)
ar2.remove(2)
ar2.remove(3)
ar3 = range(1,156)
ar3.remove(100)
ar3.remove(154)
print missingNoKetsuban(ar)
print missingNoKetsuban(ar2)
print missingNoKetsuban(ar3)

Output:

[66]
[2, 3]
[100, 154]

This function is a general solution to the Missing Numbers problem (n-size bag, k missing elements). The input is supposed to be a single array which might be unsorted, I assume that the number of missing pieces is not given as a parameter.

The array is being traversed and roughly sorted into decimal bins stored in a dictionary, in which keys encode the number of decimal units. The 10-element bins are ignored. Each remaining bin (apart from the last one) is compared to a reference range created by multiplying the key and (key+1) by 10. Values missing from a reference range are added to the output list.

The input array is supplemented with 0, this makes the first bin a 10-element set in case a missing number is not between 1 and 9.

The last bin gets a special treatment, as it might be shorter than 10.The reference range is created using key*10 and the highest number in the bin.

https://repl.it/Kmwc/3


#8

Intermediate and Hard level in Python

If both n and k are known, the task becomes somewhat easier. I convert the input array n into a set to make the search faster. Then I create a reference range assuming the min is 1 and max value is n+k, and I traverse the reference range in search of values missing from the input array/set.

def missingNoKetsuban(n,k):
    res = []
    s = set(n)
    twin = range(1,(len(n)+(k+1)))
    for number in twin:
      if number not in s:
        res.append(number)
    return res
            
ar2 = range(1,101)
ar2.remove(2)
ar2.remove(3)
ar3 = range(1,156)
ar3.remove(100)
ar3.remove(154)
print missingNoKetsuban(ar2,2)
print missingNoKetsuban(ar3,2)

Output:

[2, 3]
[100, 154]

https://repl.it/KnDM/23


#9

Here is my basic solution(python):

def missingNo(tiles):
    n = 0
    for k in range(0,99):
        n = n + tiles[k]

    # all numbers from 1 to 100 added together are 5050
    # therefore solution needs to be difference between sum of tiles(numbers) and 5050

    solution = 5050 - n
    return solution

# create array with numbers 1-100
a = []
for i in range(1,101):
    a.append(i)

a.pop(65)  # this could also be a random function for later testing

print(missingNo(a))

https://repl.it/KoO9

I’ll try the others later :slight_smile:


#10

Basic Difficulty in Python (my first ever submission!):

def missingNO(inputArray):
  #The sum of the numbers from 1 to 100 is 5050.
  #The missing number equals how much shorter than 5050 the number is.
  #inputArray must be an iterable.
  return 5050-sum(inputArray)

Testing:

testArray = list(range(1,101))
testArray.remove(66)
print(missingNO(testArray))

Output:

66

https://repl.it/KoSb/0


#11

This is my first time doing a challenge! I’m a newbie, so be nice :smiley: I did mine in JS…here’s the basic and intermediate. I attempted the hard, but I’m not sure that I did it correctly, so I’ll just leave these two here!

function missingNO(nums){
  for(var i = 1; i<=100; i++){
    if(nums.indexOf(i)===-1){
      return i;
    }
  }
}

function missingNOs(nums){
  var missing = [];
  for(var i = 1; i<=100; i++){
    if(nums.indexOf(i)===-1){
      missing.push(i);
    }
  }
  return missing;
}

The basic one just takes in the array of numbers and iterates through 1-100 to check if the number is in the original array. If it finds one that is not, it stops and returns that number.

The intermediate one works similarly, except it uses a second array and pushes any number(s) not found in the original array into the second array, then returns the second array once it has checked 1-100.

The part where I’m confused for the hard one is what arguments it would take in? Does it only take in an array like the previous two, or would it also take in n (the last number in the sequence) and k (the amount of numbers missing)? Thank you!!

Here is my code: https://repl.it/KoR3/1


#13
def missingNO(arr):
  return list(set(range(1,101)).difference(arr))

#14

I wasn’t sure if the array would be sorted, so quickly sorted at the top. Then I used a reduce function to go through the sorted array and add any missing numbers to the returned array.

const array = [1, 2, 3, 5, 10, 7]
const sort = (a, b) => a - b
const sortedArray = array.sort(sort) // no needed if presorted
const missingNumbers = sortedArray.reduce((acc, element, index) => {
	const expected = index + 1 + acc.length
	if (element !== expected) {
		// keep adding until index is equal to element
		let i = expected
		while (i < element) {
			acc.push(i)
			i += 1
		}
		return acc
	}
	return acc
}, [])


#15

Easy, intermediate and Hard Challenge in JS

Easy
repl.it

Although this challenge is substantially easier using a for loop, if we don’t know what further changes might be requested, a recursive function can make refactoring much easier. it’s also more fun to write ;o)

function MissingNO(arr) {
  var arrLength = 99; //set the length of the array
  var currentKey = arrLength - 1; //get the last key

// break out early because these values will always be constant
  if(arr[currentKey] === 99) { 
    return 100;
  } else if(arr[0] === 2) {
    return 1;
  } 
  
//use a recursive function here as it's much easier to refactor later than a standard for loop  
  function iterator(j) {
    if(arr[j] !== j + 2) {
      return j + 2;
      //our break... the difference between the 'tile' value and the key decreases by 1 when we pass the removed 'tile'. Why + 2? because our array is 0index, we then add one more to get the missing value
    }
    return iterator(j - 1); //else keep recursing through the array
  }
  return iterator(currentKey);
}

intermediate challenge JS

repl.it

instead of completely rewriting the function we only need to add some additional logic

function MissingNOs(arr) {
  
  var arrLength = 98; //set the length of the array
  var currentKey = arrLength - 1; //get the last key
  var missingNos = []; // our numbers to return
  var numbersToFind = 2; // how many numbers left to find

// break out early because these values will always be constant
  if(arr[currentKey] === 99) { 
    missingNos.push(100);
  } else if(arr[0] === 2) {
    missingNos.push(1);
  } 
  //return our function early if the missing nos are 1 and 100
  if(missingNos.length === 2) {
    return missingNos;
  }
  
//use a recursive function here as it's much easier to add logic changes later than a standard for loop  
  function iterator(j) {
    if(arr[j] !== j + numbersToFind + 1) {
      missingNos.push(j + numbersToFind + 1); //add the missing number
      
      if(missingNos.length === 2) { //set our break here
        return;
      }
    }
    return iterator(j - 1); //else keep recursing through the array
  }
  iterator(currentKey);
  return missingNos
}

Hard challenge JS
repl.it

Again the refactors are pretty simple as we set the recursive function up optimally at the ‘easy’ stage. Our initial work paid off :o). Originally I had included the code optimization but I wanted to remove it to show off how elegant recursive functions look.

function missingNoKetsuban(n, k) {
  
  var c = n.length; 
  var o = c - 1; //get the last key
  var d = []; // our numbers to return
  var e = 0; // keep track of our numbers to return

  function iterator(j) {
    if(n[j] !== j + k + 1) {
      d.push(j + k + 1);
      e++;
      if(e === k) {
        return;
      }
    }
    return iterator(j - 1); 
  }
  iterator(o);
  return d;
}

#16

Basic, Intermediate and Hard in Python 3.6

Fairly compact, sequential approach.

def missingNO(array):
#The array is missing one number no we must +1 to the length iterate over all values
  for idx in range(len(array)+1):
    #Index must start at 1 so idx+1
    if (idx+1) not in array:
      return idx+1

#Intermediate
def missingNOs(array):
  #create array to hold multiple values
  temp = []
  #Missing two values so +2 to the length
  for idx in range(len(array)+2):
    #Again, +1 to correctly index
    if (idx+1) not in array:
      temp.append(idx+1)
  return temp

#Hard
def missingNOKetsuban(array, n):
  temp = []
  #Since we know n outright, the range is fine
  for idx in range(n):
    #By now you should recognize this +1
    if (idx+1) not in array:
      temp.append(idx+1)
  return temp

#Test for Basic
array1 =[x+1 for x in range(100)]
array1.remove(66)
print(missingNO(array1))

#Test for Intermediate
array1.pop()
print(missingNOs(array1))

#Test for Hard
array1.pop(12)
print(missingNOKetsuban(array1,100))

Output:

66
[66, 100]
[13, 66, 100]

#17
# written in Ruby for hard mode + requested test case
puts "Calculate Ketsuban:"

def missing_ketsuban(bag_size, numbers_missing, bag_override=nil)
	puts "calculating the #{numbers_missing} missing number(s) in a bag of #{bag_size} numbers"
	complete_bag = (1..bag_size).to_a.shuffle
	missing_bag = bag_override ? bag_override : complete_bag.drop(numbers_missing)
	missing_numbers = complete_bag - missing_bag
	if missing_numbers.length == 1
		return missing_numbers[0]
	else
		return missing_numbers
	end
end

TEST_BAG = [(1..65).to_a, (67..100).to_a].flatten.shuffle
if missing_ketsuban(100,1,TEST_BAG) == 66
	puts "Correct"
else
	puts "Incorrect"
end


#18
function missingNoKetsuban(n, k) {
	let current = 0;
	let missings = [];
	for(let i = 1; i <= n.length+k; i++){
		if(arr[current] == i)
			current ++;
		else
			missings.push(i);
		if(missings.length == k)
			break;
	}

	return missings;
}

#19

Here goes my first attempt at a code challenge…

PHP - basic, intermediate and hard

array_diff does most of the work, I just had to add a few checks to make sure the input and output followed the instructions.

$bag = range(1,100);
$bagMissingTile = array_diff($bag, array_slice($bag, 65, 1));
$bagMissingTiles = array_diff($bag, array_slice($bag, 65, 1), array_slice($bag, 15, 1));

function missingNO($incompleteBag)
{
 if (100 - count($incompleteBag) > 1 )  return 'too many';
 $bag = range(1,100);
 return (int) implode('', array_diff($bag, $incompleteBag)); 
}

function missingNOs($incompleteBag)
{
 $bag = range(1,100);
 return array_diff($bag, $incompleteBag); 
}

function missingNoKetsuban($incompleteBag, $totalTiles)
{
 $bag = range(1,$totalTiles);
 return array_diff($bag, $incompleteBag); 
}

var_dump(missingNo($bagMissingTile));
echo "\n";
print_r(missingNos($bagMissingTiles));
echo "\n";
print_r(missingNoKetsuban($bagMissingTiles, 106));

Output:

int(66)

Array
(
    [15] => 16
    [65] => 66
)

Array
(
    [15] => 16
    [65] => 66
    [100] => 101
    [101] => 102
    [102] => 103
    [103] => 104
    [104] => 105
    [105] => 106
)

https://repl.it/Ko8H/1


#20

https://repl.it/KoiL/0

Basic difficulty:

For the basic difficulty I just used the .upto method provided by Ruby to count from 1 to 100 and in the process of counting I just created an if loop that checks if any number in the sequence doesn’t match the same one in the array given. If it does then I simply return that number.

Intermediate difficulty:

In this difficulty the only thing I had to do was add a buffer array that handled the two numbers. Because you can’t return a number into an array, I simply .push-ed the missing number into the array and after the loop I just return-ed the buffer.

Hard difficulty:

Thanks to the power of Ruby in the hard version of this code I didn’t have to change that much once again. The only thing I had to do was add an argument that specified the length of the array n and replacing the .upto number with the n variable. The k which stood up for the number of missing numbers was already handled by the previous code with that, that it simply .push-ed every missing number in the sequence, not just the specified range.


#21

https://repl.it/KoeA/7

def missingNoKetsuban(bag, size, removedCount)
  #Make an array the the same size as your bag was...
  bitVec = Array.new(size, 0) 
  
  #Iterate over the bag and flip the bit of the coresponding index (N)
  bag.map{|tile|
    bitVec[tile] = 1
  }
  
  #Iterate over your bitmap and gather non-flipped bits. (N)
  out = []
  bitVec.each_with_index{|tile, idx| 
    out << idx if tile == 0
  }
  return out
end

#Random initial bag size
sizeOfBag = Random.rand(200);
#Random number of balls
numRemovedBalls = Random.rand(sizeOfBag);
#Randomly remove the balls
bag = *(0..sizeOfBag)
bag.shuffle!.shift(numRemovedBalls)

puts "We have a bag with #{sizeOfBag} tiles."
puts "#{numRemovedBalls} were randomly removed leaving the following tiles..."
p bag
puts ""
puts "The removed tiles were..."
p missingNoKetsuban(bag, sizeOfBag, numRemovedBalls)

Solved in N speed. Works for any input sizes. Fun challenge :slight_smile:

Simple 3 step solution.

  1. Create an array of 0’s with size equal to your bag
  2. Pull tiles from the bag and mark their index as 1 ( N comparisons)
  3. Collect and return all the indexs which still have 0’s ( N comparisons)

#22

Basic/Hard

https://repl.it/KokQ