**Problem Statment :****UVA – 484 – The Department of Redundancy Department****Type :**Adhoc**Language : ANSI – C****Sol :**it can be solved using two ways.

- you can solve it using a map to map the number with it frequency and a vector indicating their order.
- or you can use it using an O(1) access solution by making adding a large displacement to the number ( as the input may contain negative numbers) this is supposed to remove the log N factor.

- but it seems for this problem that the number of distinct numbers is much much less than the input size. so the log n factor is incomparable to the cost of traversing through them all again.

#include <stdio.h> #include <string.h> #define MAX 1000002 int c[2 * MAX]; int Ns[2 * MAX]; int main() { int N, S = -1, i; for (i = 0; i < 2*MAX; ++i) c[i] = 0; while (scanf("%d", &N)==1) { Ns[++S] = N + MAX; ++c[N + MAX]; } for (i = 0; i <= S; ++i) { if (!c[Ns[i]]) continue; printf("%d %d\n", Ns[i] - MAX, c[Ns[i]]); c[Ns[i]] = 0; } return 0; }

Advertisements

I found ur map and vector technique useful 🙂