Question attached above
Hello @bratk,
So that we may help, please post the code you have written as a solution to this problem, thus far, as text, properly formatted for display. See How to ask good questions (and get good answers) for advice on how to format the code.
2 Likes
Actually, It was kind of a face to face exam. My code was totally wrong and still trying to seek out on the part where i’ve made mistake. If you didn’t get the question, I don’t mind asking you by typing.
If you post your code as well as you can remember it, we will be better able to help you find the mistake.
Edit (August 12, 2020):
Yes, please provide the question in text format so that we can see it clearly.
1 Like
Problem Statement: Given an array containing k distinct numbers taken from 0, 1, 2, … , k. Your task is to find the one that is being missing from the array.
Input Format:
- First line containing integer, denoting k
- Next k line contains array elements
Constraints:
1 <= k <= 100
0 <= arr[i] <= 100
Output Format:
single line containing the result value
Evaluation Parameters:
Sample input:
15
0
1
3
2
4
6
5
8
9
10
12
11
13
14
15
Sample Output:
7
In words, or with code, could you describe what you feel would be a good approach for solving the problem? You could explain it in terms of a function that takes k and the array of numbers as arguments and returns the missing number.
Alternatively, you could begin by considering how it could be done on paper. Then we could write code for that process.
4 Likes
Sure! I’ll say in words, I’ll create a function with array as its parameter function(array):
As it’s give constraints should be from 1-100. I’ll create a For loop that takes the numbers till 100. Now after the loop created, i’ll create a if-else condition with the missing array to be printed upon the order(index). I’ve tried this much and it did not work out for me.
1 Like
Following are some suggestions.
Also include a k parameter in the function header.
Inside the function, create a helper list for keeping track of the numbers that you find in the array, as follows:
found = [False] * (k + 1)
The indexes in that helper list range from 0 to k, inclusive.
Loop through the array of numbers. What should you do to keep track of each number that you encounter in that array?
count += 1
?
We will consider two different approaches here.
Approach 1
The list named found is for keeping track of the numbers in the array that have been encountered thus far. In other words, if a number, say 42 for example, has not yet been encountered, the element at index 42 of found is False. Prior to the for loop, none of the numbers have been encountered yet, so every element in found has been initialized to False.
As we iterate through the array in a for loop, and we find a number, say 42 for example, we can set the element at that index, 42 in this case, to True. When the loop is entirely done executing, only one element will still be False, and the index of that element is the missing number.
Let’s use the following function header:
def missing_number(k, nums):
Our array, or list, of numbers is nums.
Let’s use this loop header:
for num in nums:
Approach 2
There is also an entirely different approach that you can use for this problem that requires less coding. It involves adding up all the numbers in the array. If you do it that way, how would you use the total to find the missing number?
Try completing code for the function, using either approach described above, and post your code for us to discuss.
Edited (August 12, 2020) to discuss two approaches to the problem
1 Like
Will try implementing using approach 1 and share you the code.
Choose whichever approach you prefer. The second one might be more straightforward, if you take into account that if we are given a sequence of integers from 1 to n or from 0 to n, inclusive, the sum of those integers would be:
n * (n + 1) // 2
If one of the numbers is removed from the sequence, how would you figure out what number is missing?
The first approach could serve as a means of practicing the managing of a checklist of items, where you are iterating through a list and keeping track of some condition related to the items in the list.
1 Like
Approach 3
Another approach would be to use a Python set to save the items in the array. Checking for the presence of particular items in a set is very efficient, like accessing the items in a Python dict via the keys.
With nums representing the array, we can do the following, then use a loop to determine what number is missing from nums:
nums = set(nums)
Approach 2 Solution
My favored solution, thus far, would be to use the second approach, with the following function:
def missing_number(k, nums):
return k * (k + 1) // 2 - sum(nums)
Edited on August 16, 2020 to ask the following:
Would anyone wish to discuss or try Approach 1, Approach 3, or any other technique?
Approach 2 is the best possible imo for the following reasons:
- Fastest solution.
- O(1) space complexity - and the space it does use is also basically nothing.
- O(n) time complexity - best you can do, you need to loop over the list at least once.
- It would work for ordered and unordered array.
- Also works for slightly adjusted problem, i.e starting from 1 not 0 - more a benefit it you got the question but adjusted.
Only downside would be outside of python, in langauges were you could potentially get an overflow on the number on a large enough array. In these cases I think a bitwise Xor solution is best. This is also not an issue here because the problem limits k to 100, but should you see the problem else where or if they ask as a follow up it might be good to keep it in mind.
A bitwise approach would be something along the lines of:
def missing_number(k, nums):
xor = 0
for i in range(0, k):
xor ^= nums[i] ^ i + 1
return xor
This is also O(n) for time complexity and O(1) for space and will work with unordered arrays. But it will run slower than Approach 2 and the code will also need to be changed if the numbers start from 1 not 0. The advantage over Approach 2 being as I said above in languages/problems where overflow may be an issue this will not overflow.
There is one thing that you may have wanted to clarify (or I may have missed it):
- Is the array always ordered?
If it is always ordered you may be able to do a simpler solution. In this case we know there are multiple order agnostic solutions but on other questions - or if you cannot come up with such a solution on your own - this may be relevant.
E.g. a solution that will work only with ordered information would be:
def missing_number(k, nums):
i = 0
while(i < k):
if (i != nums[i]):
return i
i += 1
return i
This has an advantage over unordered solutions in either space (not having to keep track of what numbers have been seen) or time (not having to do an extra loop to convert to a set for faster lookup for having to do lots of look ups on a list to see if a value exists).
2 Likes
Thanks, @jagking, for the very informative analyses and solutions.
Note that in this post, the sample input is not ordered. However, a modification of the original problem that specifies that the array is ordered would define a new equally valid problem.
Edited on August 16, 2020 to add the following:
Note that k is equal to the length of the array. Accordingly, our function only needs the array as a parameter.
The solution below does not assume that the array is ordered.
def missing_number(nums):
k = len(nums)
return k * (k + 1) // 2 - sum(nums)
An edge case would be an empty array, so let’s test it. The missing number would be 0.
print(missing_number([]))
Output:
0
1 Like
Oops, my bad I glanced at them and they looked in order.
It might be worth noting that len in Python is O(1), so constant time to get the length of the list regardless of the number of items in the list. This might be worth noting because in some languages this operation is O(n), so if you was ever faced with a question where you can choose the language but the person interviewing doesn’t know Python that well it may be commented on. The function’s time complexity would still be O(n), so linear growth in time as k increases, but the actual run time would be a fair chunk slower as you are iterating over the array twice not just once. It would potentially make sense to manually loop over the array and count the size of the array and sum the values at the same time that case.
While this information may not be super helpful for OP but I’m not sure if when they say exam they could mean as part of an interview or how in depth the exam questioning regarding the code would be. It could be for others though. I’ve seen this question (or at least a variation of it) said to have been used by Amazon for at least one interview, and this the sort of extra information they would expect to know. I wouldn’t be surprised if other companies might use to too.
1 Like