Find Missing And Duplicate
Python
Medium
7 views
Problem Description
For each testcase you get n and array of size n with numbers 1..n, but one number is missing and one is repeated. Output missing and duplicate.
Input Format
First integer t. For each: n then n integers.
Output Format
t lines: missing duplicate.
Constraints
Sum of n over all testcases
Official Solution
import sys
p=sys.stdin.read().strip().split()
if not p:
sys.exit(0)
it=iter(p)
t=int(next(it))
out=[]
for _ in range(t):
n=int(next(it))
arr=[int(next(it)) for _ in range(n)]
seen=[0]*(n+1)
dup=0
for x in arr:
if 1<=x<=n:
if seen[x]:
dup=x
seen[x]=1
miss=0
for v in range(1,n+1):
if not seen[v]:
miss=v
break
out.append(f'{miss} {dup}')
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!