@misingnoglic/

"constant space" test for duplicates in list

No description

Files
• main.py
main.py
```1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
```
```# everything with a cache is commented out because its not constant lol
# prime_cache = {1: 2, 2: 3, 3:5}

def is_prime(n):
# Stolen from SO
if n==2 or n==3: return True
if n%2==0 or n<2: return False
for i in range(3,int(n**0.5)+1,2):
if n%i==0:
return False
return True

def nth_prime(n):
assert n>0  # Doesn't make sense to ask for 0th prime
# if prime_cache.get(n):
#   return prime_cache.get(n)

# # get the current prime in our cache that's closest to n
# closest_slot = 1
# closest_prime = 2
# for slot, prime in prime_cache.items():
#   if n<slot and slot>closest_slot:
#     closest_slot = slot
#     closest_prime = prime
current_checked_num = 1
current_prime = None
current_prime_num = 0
while current_prime_num!=n:
if is_prime(current_checked_num):
current_prime_num+=1
# prime_cache[current_prime_num] = current_num
current_prime = current_checked_num
current_checked_num+=1

return current_prime

def first_repeated_element_helper(nums):
# Assumes everything in nums is > 1
i = nth_prime(nums[0])
for item in nums[1:]:
n = nth_prime(item)
if i%n==0:
return item
i*=n
return None

def first_repeated_element(nums):
# We need to add everything by the min, so we can ask for the nth prime for every n in nums.
m = min(nums)
if m<1:
for i in range(len(nums)):  # Loop so it's in place
nums[i] = nums[i]+ abs(m) + 1

if m<1:
# We need to restore the answer and the list.
for i in range(len(nums)):
nums[i] = nums[i] - abs(m) - 1

assert is_prime(4)==False
assert is_prime(5)==True
assert nth_prime(1)==2
assert nth_prime(2)==3
assert nth_prime(3)==5
assert nth_prime(4)==7
assert nth_prime(5)==11
assert first_repeated_element([1, 2, 3])==None
assert first_repeated_element([1, 2, 1])==1
assert first_repeated_element([1, 1, 3])==1
assert first_repeated_element([0, 2, 1])==None
assert first_repeated_element([0, 0, 1])==0
assert first_repeated_element([-1, 0, 1])==None
assert first_repeated_element([-1, 0, -1])==-1
assert first_repeated_element(list(range(-100, 100)))==None
assert first_repeated_element(list(range(-100, 100))+[50])==50```
Fetching token