I cannot understand why this code is wrong

Question

class Solution:
    
    def firstRepeated(self,A, n):
        
        #arr : given array
        #n : size of the array
        
        D={}
        for i in range(n):
            if A[i] not in D:
                D[A[i]]=[i]
            else: 
                D[A[i]].append(i)
        c=0
        for i in D:
            if(len(D[i])>1):
                c+=1
                return (D[i][0]+1)
            
        if(c==0): return -1
       
A=[1 ,5 ,3, 4, 3, 5, 6]

n=len(A)

M=Solution()

print(M.firstRepeated(A,n))

this is a problem from geeks for geeks. " Given an array arr[] of size n, find the first repeating element. The element should occurs more than once and the index of its first occurrence should be the smallest"

the index positions(returned) are assumed to start from 1. If there is no such element that has frequency more than 1 , we gotta return -1

This code is actually working correctly in VS code, but whenever I use it in GFG IDE, it's failing(shows 3 as output instead of 2)

Kindly help, as I have no idea what's wrong here.

It's "find the first repeating element", not "find the index of the first repeated element". From your code it looks like you're returning the latter, not the former, so it might be failing one or more of the test cases. — Green Cloak Guy, Feb 14 '22 at 05:20
What Python version does this "GFG IDE" use? Your code is implicitly relying on the iteration order of dict items, which only became guaranteed in relatively recent versions. If GFG is using an older version, then your code would return a random repeating element, rather than the first. — jasonharper, Feb 14 '22 at 05:23

trincot · Accepted Answer · 2022-02-14T06:04:16.193

Your code is returning the index of the repeating element based on the order that keys are stored in the dictionary. After having collected all values in a dictionary keyed by number, your code iterates that dictionary like this:

    for i in D:

The order in which this loop will visit the dictionary keys (indexes), depends on the Python version. See Are dictionaries ordered in Python 3.6+?.

At the time of writing Geeks for Geeks uses version 3.5.2, and so the order the keys are visited is undefined, which means that sometimes your function will not return the expected answer on their web site, while on your own environment it will always be correct (if you have a more recent version).

Correction

You can change your code so it does not rely on the order of the dictionary. Instead, during insertion, check which is the dictionary key with the least value. Here is your code corrected just with that change in mind:

class Solution:
    def firstRepeated(self,A, n):
        D = {}
        c = len(A)
        for i in range(n):
            if A[i] not in D:
                D[A[i]] = i  # No need to maintain a list
            elif D[A[i]] < c: # When the dupe's first index is earlier...
                c = D[A[i]]

        if c == len(A):
            return -1
        return c + 1

This will do the trick.

score 1 · Answer 2 · answered Feb 14 '22 at 06:16

1

I checked in https://www.onlinegdb.com/online_python_compiler and works correctly. it works also in https://ide.geeksforgeeks.org/

answered Feb 14 '22 at 06:16

Ghadir Farzaneh

429
5
6

I cannot understand why this code is wrong

2 Answers2

Correction