jo sanjh khwab dekhte the

Yes, of course it can be done. Here's an idea for writing: You can save each element of the first array along with its index in an array of pairs. Then we have the Radix Sort algorithm, which sorts in O(n), with which we will sort the array of pairs. Note that so far our asymptotics are O(n). Now we will maintain the response index variable, go through the array of pairs, and while the value is equal to the next one, we will compare the indexes: the answer and the index of the current one (which we just saved in the second value of the pair). Thus, we will go over O(n), the final asymptotics is O(n).

can someone tell me if below code works for this problem or not :

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

void solve() {
    int n;
    cin >> n;

    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }

    vector<int> vis(1e5 + 5, 0);

    int ind = INT_MAX, ele = -1;
    for (int i = 0; i < n; ++i) {
        if (!vis[v[i]]) {
            vis[v[i]] = i + 1;
        } else {
            int i2 = vis[v[i]];
            if (i2 < ind) {
                ind = i2;
                ele = v[i];
            }
        }
    }

    cout << ele << endl;
}

int main() {
    solve();
    return 0;
}

I think hashing might work but I'm not sure.

To do this, you can create an empty unordered set and iterate through each element. For each element, try to find it in the set. If it’s not found, insert it in the set. If it’s found inside the set, then you’ve found the first repeating element.

You can use a bitset of size 1E9 (https://stackoverflow.com/questions/5780112/define-a-large-bitset-in-c), which uses 125 MB.

https://codeforces.net/blog/entry/129324?#comment-1147577

can we use sets??

Just use gp_hash_table. It's a O(1) hashtable.

The best algorithm that I made by this time works in O($$$n\cdot log_n(max A)$$$). But with this restrictions it will work in linear time. First of all, we can make all numbers positive. Just find minimum of the array and add to all elements. We do not care about exact element, but we care about it's index. Then, if maximum of array is less or equal to $$$n$$$, we can do it in O($$$n$$$) just iterating through array and memorizing in the array index of first occurents. Otherwise, we can try to compress elements. Make array of $$$n$$$ elements and name it (let it be b). Then $$$b[x]$$$ is array of elements from the array $$$a$$$ with remainder $$$x$$$ after dividing by $$$n$$$. In other words, $$$b[x]$$$ has all elements $$$a[i]$$$, such that a[i]%n=x. We can do it in linear time. Now we can go in each such $$$x$$$ where $$$b[x]$$$ is non-empty, and if $$$b[x][i]$$$ equal to $$$x+n*k$$$ for some $$$k$$$, we can replace it by $$$k$$$. In such way, all elements that are equal will remain equal and not equal not equal. Also, it make $$$max A$$$ decrease in $$$n$$$ times at least. Then we can apply recursevily this algorithm for each $$$x$$$, such that $$$b[x]$$$ is non-empty.

We cannot use master theorem to analyze this recursion, but we can write out recursive tree and get that branch factor is at most $$$n$$$ but number of elements in each recursion is also at most $$$n$$$, so the time spent on each level is $$$O(n)$$$ and there are at most $$$log_n(maxA)$$$ levels, because we decrease $$$maxA$$$ in $$$n$$$ times at least on each level, so total time is $$$O(n\cdot log_n(maxA))$$$.

ok

.