0
$\begingroup$

I have the following problem to solve:

Given a non-empty array A consisting of N integers, the task is to find the first unique number in the array. A unique number is defined as a number that occurs exactly once in the array. The desired output is the unique number with the lowest position in the array.

For example, consider the following array A:

   A[0] = 4
   A[1] = 10
   A[2] = 5
   A[3] = 4
   A[4] = 2
   A[5] = 10

In this array, the unique numbers are 5 and 2. The first unique number with the lowest position is 5 because A[2] = 5.

The problem requires an algorithm and the time complexity for finding the first unique number in the given array. The algorithm should be able to handle a generic case where the given array A can have any size N and any set of integers.

$\endgroup$
3
  • 1
    $\begingroup$ What have you tried to solve this problem? $\endgroup$
    – Russel
    Jan 13 at 10:48
  • 1
    $\begingroup$ What is your question ? $\endgroup$ Jan 13 at 10:51
  • $\begingroup$ @Russel Im trying to find an algorithm that solves the issue and its time complexity $\endgroup$ Jan 13 at 10:57

2 Answers 2

0
$\begingroup$

Here's one idea.

  1. Pair up each element with its index.

     [(4, 0), (10, 1), (5, 2), (4, 3), (2, 4), (10, 5)]
    
  2. Sort.

     [(2, 4), (4, 0), (4, 3), (5, 2), (10, 1), (10, 5)]
    
  3. It is now easy to recognize unique elements, because if any duplicates exist they are right next to each other. Keep only the unique elements.

     [(2, 4), (5, 2)]
    
  4. Sort again but on the other half of the pair.

     [(5, 2), (2, 4)]
    
  5. Take the first result.

$\endgroup$
0
$\begingroup$

Simples. Use a hash table. Fill it with a[n-1], a[n-2] ... a[0] in that order. When you add a number to a hash table you will know if it was there already or not. What you want is the last number you added that wasn't in the hash table before you added it.

(It is obvious that you need to examine all array elements, because one that you don't examine could contain the same value as the array element that you thought was the first unique one, and you would get the wrong answer).

A hash table of reasonable size will work in constant times average.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.