The problem is from codeforces: http://www.codeforces.com/problemset/problem/137/B
It took me several attempts to get it right for this problem although it is not difficult. The problem is find out how many alterations (minimal) required to transform a integer sequence to its permutation (each number appears exactly only once).
The biggest trap is that: the input item may not be needed at all (out of the range of [1, n]), in this case, you increment the counter.
The algorithm is to maintain a list (initialised empty) and use this to keep the numbers that are needed. The second time a same number appears or the number is out of range, we increment the counter. The first time an valid number appears, we simply append it to the list.
The Python solution, after several improvments is presented below. Simpler and more elegant!
n = int(raw_input())
s = raw_input().split(" ")
ss = map(int, s)
ans = 0
i = 0
k = []
while i < n:
if s[i] in k or ss[i] > n:
ans += 1
else:
k.append(s[i])
i += 1
print ans
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: The 'any' keyword in Python
Next Post: Copy by reference or value in Python
