0
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ I don't have time to write a full answer, but it comes down to this: you have a turned an O(n) problem into an O(n^2) problem. Here is the algorithm I would use: create a list of bools that is the size of number_array. Initialize the elements to false with a list comprehension. Now, iterate through number_array. For each number found, check the value in the bool list at that index - 1. If it's true, add that number to the output list. If it's false, set it to true. Then iterate through the list of bools. Once you find an element that is false, add the index of that element + 1 to the... \$\endgroup\$ – Mike Borkland Jun 24 '18 at 15:51
  • \$\begingroup\$ output list. Break from the loop and return the output list. \$\endgroup\$ – Mike Borkland Jun 24 '18 at 15:51
  • 1
    \$\begingroup\$ Did you do some research? Various more efficient methods are demonstrated for example at geeksforgeeks.org/find-a-repeating-and-a-missing-number and stackoverflow.com/questions/5766936/…. – And here is another CR question about the same problem codereview.stackexchange.com/questions/194379/… \$\endgroup\$ – Martin R Jun 24 '18 at 16:05
  • 1
    \$\begingroup\$ @MartinR my bad, I should have checked. \$\endgroup\$ – Prathu Baronia Jun 24 '18 at 16:16
  • \$\begingroup\$ I actually solved by having an empty hashmap and started populating it as I proceeded and had a check on whenever the value goes to 2 \$\endgroup\$ – Prathu Baronia Jun 28 '18 at 11:45
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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}

\$\endgroup\$
  • \$\begingroup\$ You're right, added my solution for B value. \$\endgroup\$ – sardok Oct 14 '18 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.