@misingnoglic/

"constant space" test for duplicates in list

Python

No description

fork
loading
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
  
  answer = first_repeated_element_helper(nums)

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


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