Finding Repeat and missing numbers in an array

Question

Problem Statement:

You are given a read-only array of n integers from 1 to n. Each integer appears exactly once except A which appears twice and B which is missing.

Return A and B.

Example

Input:[3 1 2 5 3] 
Output:[3, 4] 
A = 3, B = 4

I wrote the following code:

def repeated_number(number_array):

   pair_A_B = []

   n = len(number_array)

   for i in number_array:
      if(number_array.count(i)==2):
        pair_A_B.append(i)
        break

   sample = range(1,n+1)

   diff = list(set(sample)-set(number_array))

   pair_A_B.append(diff[0])

   return pair_A_B

sample_input = [3,1,2,3,5]

print(repeated_number(sample_input))

The code works fine for this problem on my laptop but when I try to submit it on a coding forum it says my code is not efficient. How can I make it efficient in terms of time?

Answer 1

The problem lies in these 2 lines of code:

 for i in number_array:
  if(number_array.count(i)==2):

Here for each number you are counting the number of occurrences in the array. Now, by doing that, You are reiterating over the numbers which are already counted. The call to number_array.count() searches the entire array, which means even for the last element, it will start from the first and calculate the count. This makes the time complexity \$O(n^2)\$. But, it can be done in \$O(n)\$ time.

Instead of using count, store the numbers in a hash table. And for each new number check, if it already exists in the hash table. If so, that's your duplicate number - A.

Also, while iterating through the loop, add each number to the other, and get their sum (omitting the double occurrence of A). And since you have a series from 1..n,

sum(1..n) = n * (n + 1) / 2

So, the missing number is:

sum(1..n) - actual sum

Answer 2

In addition to answers given here, you may use collections module for more pythonic code to find A.

import collections

[k for k, v in collections.Counter([1,2,3,3,5]).items() if v > 1]
# [3]

This is O(n).

In order to find B, you may consider using something, assuming given list is named as xs.

{*range(min(xs), max(xs) + 1)} - {*xs}