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

Question

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

why you put the function inside a class? for this specific request you can just use a function with def — NicoCaldo, Jul 11 '22 at 12:11
because i am solving it on a platform on which i needed to just solve the function — Vishav Singla, Jul 11 '22 at 12:12
Programming is not math, you can't omit the `*` when multiplying `(n(n+1))//2`, it needs to be `(n*(n+1))//2`. This would be even more obvious if you had posted the traceback as part of the [MCVE] like you're supposed to. — ShadowRanger, Jul 11 '22 at 12:13
Aha, this is a variant on the Lonely Number problem - the standard version of this is that a stream of N numbers will feature around N/2 numbers where there are two of one number, and there will be one instance of a single ("lonely") number. — halfer, Jul 11 '22 at 12:17
You can try keeping tabs on what numbers turn up, but I wonder if there is a bitwise solution, which will have O(N). — halfer, Jul 11 '22 at 12:18

score 1 · Answer 1 · edited Jul 11 '22 at 14:50

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

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.

dont use inbuild function name for object name – sahasrara62 Jul 11 '22 at 12:29 — sahasrara62, Jul 11 '22 at 12:29
Alright I'll edit that in, thanks! – Marco Kurepa Jul 11 '22 at 12:31 — Marco Kurepa, Jul 11 '22 at 12:31

score 0 · Accepted Answer · edited Jul 11 '22 at 16:18

0

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

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

length = len(my_list)

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

for x in range(1,length+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 length. 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)

edited Jul 11 '22 at 16:18

halfer

19,824
17
99
186

answered Jul 11 '22 at 12:19

NicoCaldo

1,171
13
25

I wonder if this might be too helpful, to the degree that the OP can now cheat on something. It's generally best to help them learn instead if you can. – halfer Jul 11 '22 at 12:21
it is O(n*n), did you not consider list.remove time complexity ? – sahasrara62 Jul 11 '22 at 12:22
@sahasrara62 I'm not considering it, should I? – NicoCaldo Jul 11 '22 at 12:23
yes you should consider it – sahasrara62 Jul 11 '22 at 12:23
@sahasrara62 ok, I thought the assignment wouldn't taake into consideration inbuilt python function – NicoCaldo Jul 11 '22 at 12:26
Be careful, you shouldn't write O(2n) but O(n). Edit: in your edit, time complexity is O(n^2) not O(n + n^2) – Pauuuuuuul Jul 11 '22 at 12:27
i think its using more space as u initialised a new list – Vishav Singla Jul 11 '22 at 12:31
@Pauuuuuuul why? there are two for loops, each of them run n time – NicoCaldo Jul 11 '22 at 12:31
yup time complexity is all right – Vishav Singla Jul 11 '22 at 12:33
That's not how the Big O notation works. If you had k for loops of time complexity O(n) (where k is a constant), the overall complexity of your program would still be O(n). – Pauuuuuuul Jul 11 '22 at 12:36
@Pauuuuuuul _O(k*n)_ is more accurate as you get more info. At least this is what have taught me at Uni – NicoCaldo Jul 11 '22 at 12:39
1

Assuming k is a constant (as I specified in my previous comment), you don't add any info writing O(k*n), time complexity is still linear with respect to the size of the input so you should write O(n). Look at this as I it is better explained than what I could come up with in the comment section: [Which algorithm is faster O(N) or O(2N)?](https://stackoverflow.com/questions/25777714/which-algorithm-is-faster-on-or-o2n) – Pauuuuuuul Jul 11 '22 at 12:44

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

2 Answers2