Find the non duplicate element

There is an array in which except one element, all other elements have duplicates, find that non duplicate element.

Answer:

/**
 * An array in which all elements except one are duplicate.,
 * find that element
 * */
#include "vector"
#include "algorithm"
#include "stdio.h"
using namespace std;

/** SOLUTION I 
 * Sort the array - O(n log(n))
 * Find the duplicate - O(n) (single pass)
 * */
void SortAndFind(vector &vec)
{
    // O(n log(n))
    sort(vec.begin(), vec.end() );
    int i = 0;
    int j = i + 1;
    int n = vec.size();
    // O(n)
    for ( i = 0, j = i+1; j < n ; ++j)
    {
        if ( vec[j] != vec[i] )
        {
            if ( (j-i) == 1 )
            {
                /* non duplicate found at j */
                printf("\n Non Duplicate (%s) %d \n", __func__, vec[i]);
                return;
            }
            else
            {
                i=j;
            }
        }
    }
    // the last element is the duplicate
    printf("\n Non Duplicate (%s) %d \n", __func__, vec[n-1]);
}

/** SOLUTION II , better than first solution.
 * Heapify the array - O(n)
 * Remove one element at a time and find the duplicate - O(log(n))
 * This approach is better because there is no need to sort the entire array
 * */
void HeapifyAndFind(vector &vec)
{
    // Create the heap O(n)
    make_heap(vec.begin(), vec.end() );
    // Find the duplicate, by removing one element at a
    // time.
    //
    int i = 0;
    int n = vec.size();
    for ( int j = i+1; j < n; ++j)
    {
        // vec[j-1] is the min element
        make_heap( vec.begin() + i , vec.end() );
        if ( vec[i] != vec[j] )
        {
            if ( (j-i) == 1 )
            {
                /* non duplicate found at j */
                printf("\n Non Duplicate (%s) %d \n", __func__, vec[i]);
                return;
            }
            else
            {
                i=j;
            }
        }

    }
    // the last element is the duplicate
    printf("\n Non Duplicate (%s) %d \n", __func__, vec[n-1]);

}

int main(int argc, char *argv[])
{
    if ( argc > 1 )
    {
        vector vec1(argc-1);
        vector vec2(argc-1);

        for (int i = 1; i <= argc-1; ++i)
        {
            vec1[i-1] = atoi(argv[i]);
            vec2[i-1] = atoi(argv[i]);
        }

        SortAndFind( vec1 );
        HeapifyAndFind( vec2 );
    }
    return 0;
}

Second minimum element in a array

Given an array of n numbers a[1], a[2],..., a[n], find the second minimum number in n + log n comparisons.

Answer:


Initially it seems that this can be done in a single pass,
like finding the min element, but dont be tricked, this is not possible.
For example, if the second min happens first and the min element happens later,
then its not possible, ex: {10, 6, 9, 7, 8, 5}

The answer is in fact is in the question itself,
Build a Min Heap - O(n) time
Remove the Root - O(log(n)) time
Remove the Root again, which happens to be the second min element - O(log(n))

So the total time = n + log(n)


See also:
*Selection Sort technique

Heap problem

Consider a binary heap containing n numbers (the root stores the greatest number). You are given a positive integer k < n and a number x . You have to determine whether the kth largest element of the heap is greater than x or not. Your algorithm must take O(k) time. You may use O(k) extra storage.

Solution:

The Heap has n elements,

n n-1 n-2 .....k....3 2 1
               ^^^^^^^^^^
               The Kth largest element happens somewhere in this range, 
               because it is a heap, and every parent >= child.

Possible solution, copy the last k elements to the temporary structure,
and build a heap which will take O(k) time and compare the root with the number x.