I went thru this problem on geeksforgeeks.com and while my solution managed to pass all test cases, I actually used .sort() so I know it doesn't fit the Expected Time Complexity of O(n): I mean we all know no sorting algorithm works on O(n), not even the best implementation of Timsort (which is what Python uses). So I went to check the website's Answer/Solution and found this:
def printRepeating(arr, n):
# First check all the
# values that are
# present in an array
# then go to that
# values as indexes
# and increment by
# the size of array
for i in range(0, n):
index = arr[i] % n
arr[index] = n
# Now check which value
# exists more
# than once by dividing
# with the size
# of array
for i in range(0, n):
if (arr[i]/n) >= 2:
print(i, end=" ")
I tried to follow the logic behind that algorithm but honestly couldn't, so I tested different datasets until I found that it failed for some. For instance:
arr = [5, 6, 3, 1, 3, 6, 6, 0, 0, 11, 11, 1, 1, 50, 50]
Output: 0 1 3 5 6 11 13 14
Notice that:
- Number 5 IS NOT repeated in the array,
- Numbers 13 and 14 are not even present in the array, and
- Number 50 is both, present and repeated, and the solution won't show it.
I already reported the problem to the website, I just wanted to know if, since these problems are supposed to be curated, there is a solution in O(n). My best guess is there isn't unless you can somehow insert every repeated number in O(1) within the mapping of all keys/values.
CodePudding user response:
The reason the code doesn't work with your example data set is that you're violating one of the constraints that is given in the problem. The input array (of length n
) is supposed to only contain values from 0
to n-1
. Your values of 50 are too big (since you have 15 elements in your list). That constraint is why adding n
to the existing values doesn't break things. You have a less-than-n original value (that can be extracted with arr[i] % n
), and the count (that can be extracted with arr[i] // n
). The two values are stacked on top of each other, cleverly reusing the existing array with no extra space needed.
CodePudding user response:
The problem can be solved with dict()
.
And for Python here: https://docs.python.org/3.10/library/stdtypes.html#mapping-types-dict
It's an abstract data type that accesses in amortized O(1), which as you've mentioned, is exactly what you need.
Python stdlib also has collections.Counter, which is a specialization of dict
that accomplishes 90% of what the problem asks for.
edit
Oh, the results have to be sorted too. Looks like they want you to use a list()
"as a dict
", mapping integers to their number of occurrences via their own value as an index.