Home/

...

/

Introduction

Introduction

Dry-run templates

The following is the implementation of the solution provided for the Find all Missing Numbers (easy) problem:

Press + to interact
Python 3.5
def find_missing_numbers(nums):
  i = 0
  while i < len(nums):
    j = nums[i] - 1
    if nums[i] != nums[j]:
      nums[i], nums[j] = nums[j], nums[i]  # swap
    else:
      i += 1
  missingNumbers = []
  for i in range(len(nums)):
    if nums[i] != i + 1:
      missingNumbers.append(i + 1)
  return missingNumbers
def main():
  print(find_missing_numbers([2, 3, 1, 8, 2, 3, 5, 1]))
  print(find_missing_numbers([2, 4, 1, 2]))
  print(find_missing_numbers([2, 3, 2, 1]))
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample Input #1

nums: [2, 3, 1, 8, 2, 3, 5, 1]

Iteration No.

Line No.

i

j

nums[i]

nums[j]

nums

missingNumbers

-

2

0

-

-

-

[2, 3, 1, 8, 2, 3, 5, 1]

-

1

5

0

1

2

3

[2, 3, 1, 8, 2, 3, 5, 1]

-

1

6

0

1

2

3

[3, 2, 1, 8, 2, 3, 5, 1]

-

2

5

0

2

3

1

[3, 2, 1, 8, 2, 3, 5, 1]

-

2

6

0

2

3

1

[1, 2, 3, 8, 2, 3, 5, 1]

-

3

5

0

0

1

1

[1, 2, 3, 8, 2, 3, 5, 1]

-

4

5

1

1

2

2

[1, 2, 3, 8, 2, 3, 5, 1]

-

5

5

2

2

3

3

[1, 2, 3, 8, 2, 3, 5, 1]

-

6

5

3

7

8

1

[1, 2, 3, 8, 2, 3, 5, 1]

-

6

6

3

7

8

1

[1, 2, 3, 1, 2, 3, 5, 8]

-

7

5

3

0

1

1

[1, 2, 3, 1, 2, 3, 5, 8]

-

8

5

4

1

2

2

[1, 2, 3, 1, 2, 3, 5, 8]

-

9

5

5

3

3

3

[1, 2, 3, 1, 2, 3, 5, 8]

-

10

5

6

4

5

2

[1, 2, 3, 1, 2, 3, 5, 8]

-

10

6

6

4

5

2

[1, 2, 3, 1, 5, 3, 2, 8]

-

11

5

6

1

2

2

[1, 2, 3, 1, 5, 3, 2, 8]

-

12

5

7

7

8

8

[1, 2, 3, 1, 5, 3, 2, 8]

-

4

14

3

-

1

-

[1, 2, 3, 1, 5, 3, 2, 8]

[4]

6

14

5

-

3

-

[1, 2, 3, 1, 5, 3, 2, 8]

[4,6]

7

14

6

-

2

-

[1, 2, 3, 1, 5, 3, 2, 8]

[4,6,7]

Sample Input 2

nums: [2,3,1,2,3,1]

Students may be encouraged to complete the dry-run with this input:

Iteration No.

Line No.

i

j

nums[i]

nums[j]

nums

missingNumbers

-

2

0

-

-

-

[2, 3, 1, 2,3,1]

-

1

5

0

1

2

3

[2, 3, 1, 2,3,1]

-

1

6

0

1

2

3

[3, 2, 1, 2, 3, 1]

-

2

5

0

2

3

1

[3, 2, 1, 2, 3, 1]

-

2

6

0

2

3

1

[1, 2, 3, 2, 3, 1]

-

...

...

...

...

...

...

...

...

Trace Generation

Press + to interact
Python 3.5
def find_missing_numbers(nums):
  i = 0
  while i < len(nums):
    j = nums[i] - 1
    print("\ti: ",i,end="          ")
    print("nums[i]",nums[i],sep=" ")
    print("\tj: ",j,end="          ")
    print("nums[j]",nums[j],sep=" ")
    if nums[i] != nums[j]:
      nums[i], nums[j] = nums[j], nums[i]  # swap
      print("\t" + str(nums[i]) + " and " + str(nums[j]) + " swapped ")
      print("\tnums after swap: " + str(nums))
    else:
      print("\tSame values, no need to swap.")
      i += 1
  missingNumbers = []
  print("\tTraversing " + str(nums) + " to find missing numbers")
  for i in range(len(nums)):
    if nums[i] != i + 1:
      print("\t"+str(nums[i]) + " != " + str(i+1))
      print("\tMissing number FOUND: Appending " + str(i+1) + " to missingNumbers")
      missingNumbers.append(i + 1)
  return missingNumbers
def main():
  nums_arr = [[2, 3, 1, 8, 2, 3, 5, 1],[2, 4, 1, 2],[2, 3, 2, 1]]
  for i in nums_arr:
    print("Finding missing numbers in: " + str(i))
    result = find_missing_numbers(i)
    print("Missing numbers are: " + str(result))
    print(("-"*100)+"\n")
  
main()