01204212/id request

This is part of 01204212

An API requires every user to have a unique ID. To ensure that it provides an interface to check and allocate IDs. There are N requests; each request specifies an ID x, which is an integer from 0 up to 1,000,000,000. For each request, your program have to answer if x has been used. In the case where x is new, it allocates that integer for the requested user. Initially, no ID has been used.

Input

• First line: an integer N (1<=N<=100,000)
• The next N lines: each line contains an integer x

Output

There are N lines of output, each contains either Y (if the requested ID has been used before) or N (if the requested ID is new)

Example

Input

10
4
2
4
10
100
30
10
35
100
200

Output

N
N
Y
N
N
N
Y
N
Y
N

Test data

Download at: here

Solution to n10.in

N
N
N
N
N
N
N
Y
N
Y

Solution to n1000.in (first 20 lines)

N
N
N
N
N
Y
N
N
N
N
N
Y
Y
N
Y
N
Y
Y
N
N

Code

Collection choices

• TreeSet
• HashSet
• Implementation of "static" sets with binary search

Main method

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    int n;
    int[] xs;
    
    public static void main(String[] args) throws Exception {
        Main m = new Main();
        
        m.readInput();
        m.process();
    }

    private void process() {    
        // your code here
    }
    
    private void readInput() throws Exception {
        BufferedReader reader = new BufferedReader(
                   new InputStreamReader(System.in) );

        n = Integer.parseInt(reader.readLine());
        xs = new int[n];

        for(int i=0; i<n; i++) {
            xs[i] = Integer.parseInt(reader.readLine());
        }

    }
}

Code for the static version (using binary search)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class Main {

    int n;
    int[] xs;
    
    int[] keys;
    int[] values;
    int keyCount;
    
    public static void main(String[] args) throws Exception {
        Main m = new Main();
        
        m.readInput();
        m.process();
    }

    private void process() {    
        buildKeyArray();
        for(int i=0; i<n; i++) {
            int x = xs[i];
            int idx = _______________________;  // your call to binary search here
            if(values[idx] == 0) {
                System.out.println("N");
                values[idx] = 1;
            } else {
                System.out.println("Y");                
            }
        }
    }
    
    private int binarySearch(int x) {
        // .....  your code here
    }

    private void buildKeyArray() {
        int[] allKeys = new int[n];
        for(int i=0; i<n; i++) {
            allKeys[i] = xs[i];
        }
        Arrays.sort(allKeys);
        
        //count non-dup keys
        int c = 1;
        for(int i=1; i<n; i++) {
            if(allKeys[i] != allKeys[i-1]) {
                c++;
            }
        }
        keyCount = c;
        keys = new int[keyCount];
        values = new int[keyCount];
        
        keys[0] = allKeys[0];
        c = 1;
        for(int i=1; i<n; i++) {
            if(allKeys[i] != allKeys[i-1]) {
                keys[c] = allKeys[i];
                c++;
            }
        }
    }

    private void readInput() throws Exception {
        BufferedReader reader = new BufferedReader(
                   new InputStreamReader(System.in) );

        n = Integer.parseInt(reader.readLine());
        xs = new int[n];

        for(int i=0; i<n; i++) {
            xs[i] = Integer.parseInt(reader.readLine());
        }
    }
}