# 12436 - Hulk's Trouble
>author: Utin
###### tags: `qsort`

---

## Brief
See the code below

## Solution 0

#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
    int id, amount;
} Node;

int input[100005], input_len = 0, len = 0, q;
Node arr[100005];
int cmp(const void* a, const void* b);
int search(int l, int r, int target);

int main() {
    
    // get input and sort the data
    scanf("%d", &input_len);
    for (int i = 0; i < input_len; i++) 
        scanf("%d", &input[i]);
    qsort(input, input_len, sizeof(int), cmp);

    // construct a lookup table
    int start = 0, end = 0;
    for (int i = 0; i <= input_len; i++) {
        end = i;
        if (start >= end) start = i;
        if (input[start] != input[i]) {
            arr[len].id = input[start];
            arr[len].amount = i - start;
            len++;
            start = end;
        }
    }

    // search
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        int tmp;
        scanf("%d", &tmp);
        printf("%d\n", search(0, len, tmp));
    }
    
}

// comparison function for qsort
int cmp(const void* a, const void* b) {
    return *(int*) a - *(int*) b;
}

// searching function
int search(int l, int r, int target) {
    int idx = (l + r) / 2;
    if (target == arr[idx].id) return arr[idx].amount;
    if (l == r) return 0;
    if (l == r - 1) return search(l, l, target) | search(r, r, target);
    if (target < arr[idx].id) return search(l, idx, target);
    if (target > arr[idx].id) return search(idx, r, target);
}

// By Utin

## Reference