Cant find what's wrong in the code... Repeat and missing Number-CodePudding

Question

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.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Note that in your output A should precede B.

Example:

Input:[3 1 2 5 3] 

Output:[3, 4] 

A = 3, B = 4

My code:

class Solution:
    def repeatedNumber(self, A):
        n=len(A)
        asum=0
        rsum = (n*(n 1))//2
        x=0
        dict={}
        for i in A:
            asum =A[i]
            
            if A[i] in dict:
                x=A[i]
            else:
                dict[i]=1

        
        diff=rsum-asum
        
        return x,x diff

CodePudding user response：

Your error is simple, you're using for i in A: but you refer to i within the for loop as if you did for i in range(len(A)):. To fix this all you need to do is replace all instances of A[i] in your code with i. It should look something like this:

class Solution:
    def repeatedNumber(self, A):
        n=len(A)
        asum=0
        rsum = (n*(n 1))//2
        x=0
        distinct={}
        for i in A:
            asum =i
            
            if i in distinct:
                x=i
            else:
                distinct[i]=1

        
        diff=rsum-asum
        
        return x,x diff

I hope that helped:)

Note: It doesn't have any functional relevance in this case, but it is generally go practice to name your variables something other than the object name. In this case I just renamed the dict variable to distinct, as it also gives readers a better understanding of what the dictionary is actually used for.

CodePudding user response：

This could be a solution. It runs in O(2n)

my_list = [3, 1, 2, 5, 3]
new_list = []

lenght = len(my_list)

for x in range(1,lenght 1):
  new_list.append(x)

for x in range(1,lenght 1):
  try:
    my_list.remove(x)
  except:
    missing_number = x
    
double_number = my_list[0]

print(missing_number)
print(double_number)

Basically, according to your input, you can use the fact that the max value inside the list is the max lenght. So you create a new list with all the possible values, scan your first list and removing the values from the second list. If you try to remove a value that doesn't exist in the list you got error (that's why the try, except) and at the end you get, in the original list, only the double value (as it has been removed just one time)

EDIT: actually, if you consider the execution time of .remove() function, the overall running time of the function is O(n n^2)