from typing import Optional
def solve(n: int, k: int, a: list[int]) -> Optional[int]:
for i in range(n):
for j in range(n):
if i == j:
continue
if (a[i] - a[j]) % k == 0:
break
else:
return i + 1
return False
for _ in range(int(input())):
n, k = map(int, input().split())
a: list[int] = list(map(int, input().split()))
if ans := solve(n, k, a):
print("YES")
print(ans)
else:
print("NO")My solution to this problem involves checking the condition naively,
but as the editorial suggests, we can focus on mod
instead.
| x - y | is divisible by k <=> x mod k == y mod k
for _ in range(int(input())):
n, k = map(int, input().split())
a: list[int] = list(map(int, input().split()))
d: dict[int, int] = {}
for i in range(n):
if a[i] % k not in d:
d[a[i] % k] = [i + 1]
else:
d[a[i] % k].append(i + 1)
for mod, vals in d.items():
if len(vals) == 1:
print("YES")
print(vals[0])
break
else:
print("NO")By using O(n) space, we managed to reduce the time complexity O(n^2) -> O(n).
dictionary. I have no idea what is happening here
now._ lb
Egg Rice 10 g Boba 40 g McDonald’s 40 g Protein shake 50 g
total protein -> 140 g (>= 140)