educative.io

Find the Missing Number

Courses
,
#1

Hello, I’m wondering about the part of the problem where we are comparing with the value of nums[j]. In the example, [4, 0, 3, 1], the value i starts at zero. But the value at nums[i] will give us an index for j, which is out of bounds. Here’s how I"m walking through it.

i = 0, then j = nums[i] which is 4

Then in the if-statement, we have a comparison involving nums[j], in this case, it’s nums[4] which is out of bounds, since the array only goes up to index 3. In the if-statement, is nums[j] treated as None (or null)? So we’re comparing nums[i] to None (or null)?

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Find the Missing Number (easy) - Grokking the Coding Interview: Patterns for Coding Questions

#2

Hi @Jeremy1,
The actually statement is
const j = nums[i] - 1;
due to -1 it does not go out of bound.

Please let me know if it is still confusing.

#3

Not understanding this. The solution code writes on line 4 (of Python3 version) that j = nums[I], not that j = nums[I] - 1.

And to @Jeremy1 point, this will result in:

i = 0
j = nums[i] = nums[0] = 4
nums[j] = nums[4], which is out of bounds

Any help would be greatly appreciated!

#4

In the if statement we have

if nums[i] < n and nums[i] != nums[j]

Since the first condition is “if nums[i] < n”, the entire if statement fails when j = nums[i] = 4. You can test this if you swap the order to the below, you’ll get an out of bounds error.

nums[i] != nums[j] and if nums[i] < n

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Find the Missing Number (easy) - Grokking the Coding Interview: Patterns for Coding Questions

#5

Hi @Eric_Onofrey ,
Yes, you are right. It will go out of bounds. Following is the updated code of find_missing_number function;

def find_missing_number(nums):
  i, n = 0, len(nums)
  while i < n:
  j = nums[i]
    if j == n:
      j = j-1
    if nums[i] < n and nums[i] != nums[j]:
      nums[i], nums[j] = nums[j], nums[i]  # swap
    else:
      i += 1

Now it will not go out of bounds. I hope it will help. Please drop us a note if you have any other questions or concerns.

#6

Hi @Anura_Ranasinghe
Yes, you are right. It will go out of bounds. Following is the updated code of find_missing_number function;

def find_missing_number(nums):
  i, n = 0, len(nums)
  while i < n:
  j = nums[i]
    if j == n:
      j = j-1
    if nums[i] < n and nums[i] != nums[j]:
      nums[i], nums[j] = nums[j], nums[i]  # swap
    else:
      i += 1

Now it will not go out of bounds. I hope it will help. Please drop us a note if you have any other questions or concerns.