Say, for each number in a list, whether it has already appeared.
What to build
A lookup by value that takes one step for each number.
Requirements
- Print
newthe first time a number appears. - Print
seenevery time it appears after that. - Do not search the earlier numbers with a loop.
Input
The first line has n. The second line has the n numbers.
Output
One line for each number.
Constraints
1 ≤ n ≤ 1000, and each number is from 0 to 1000.
Example
Input:
5
3 7 3 3 9
Output:
new
new
seen
seen
new
Why it works
When the keys are small whole numbers, the key itself can be the index. That is a hash table with no collisions, and it is the simplest structure that makes this lookup O(1).
Examples
Example 1 · Input
5 3 7 3 3 9
Expected output
new new seen seen new
Example 2 · Input
1 0
Expected output
new
Hints
Hint 1
Every number is from 0 to 1000, so an array of 1001 flags has one cell for each possible number.
Hint 2
Check the number's flag, print the answer, then set the flag.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int seen[1001];
int main(void) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
if (seen[x]) {
printf("seen\n");
} else {
printf("new\n");
seen[x] = 1;
}
}
return 0;
}