CareerCup

package com.algorithm.amazon;


public class RemoveAdjacentPairs {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = { 1, 1, 2, 3,3, 4, 5 };
		removeAdjPairs(arr);
	}

	private static void removeAdjPairs(int[] arr) {
		// TODO Auto-generated method stub
		int j = 0,len=arr.length;
		for (int i = 1; i < arr.length; i++) {
			while(j >= 0 && arr[j] == arr[i] ) {
				len--;
				i++;
				j = j <= 0 ? 0 : j - 1;
			}
			
				arr[++j]=arr[i];
		}
		for (int i = 0; i < len; i++) {
			System.out.println(arr[i]);
		}
	}

}

int removeDuplicates ( int Arr[], int Len ) {
  if ( Len <= 1 )
		return Len ;
		
	int Index = 0, Itr = 1 ;
	
	while ( Itr < Len ) {
		if ( Arr[Itr] != Arr[Index] )
			Arr[++Index] = Arr[Itr] ;
		
		Itr++ ;
	}
	
	return ( Index + 1 );
}

Method returns the Index to the End of Distinct Elements in the Array.

public static int[] adjust(int[] ar) {		
		if(ar == null || ar.length < 2)
			return ar;
		
		int read;
		int write;
		
		for(read = 1, write = 0; read < ar.length; ) {
			if (ar[read] == ar[write]) {
				read++;
				continue;
			} else {
				write++;
				int temp = ar[write];
				ar[write] = ar[read];
				ar[read] = temp;
				read++;
			}
		}
		
		return ar;
	}

We do this by using a hash map.

//Given an array of sorted elements, move the distinct values to the top
	var arr = [1,1,2,2,3,4,5];

	function moveDistinct(arr){

		var indexMap = {};

		//Mark the duplicates
		for(var i = 0; i < arr.length; i++){

			var value = arr[i];
			if(indexMap[value]  > 0){

				indexMap[value]++;
			}
			else{
				indexMap[value] = 1;
			}
		}

		//replace front values of array with distinct values
		var count = 0;
		for(var key in indexMap){

			if(indexMap.hasOwnProperty(key)){

				if(indexMap[key] === 1){

					arr[count] = parseInt(key);
					count++;
				}
			}
		}

		//add the duplicate values back in
		for(var key in indexMap){

			if(indexMap.hasOwnProperty(key)){

				if(indexMap[key] > 1){

					// add each occurrence to the array after the last distinct value
					
					while(indexMap[key] > 0){
						arr[count] = parseInt(key);  
						count++;
						indexMap[key]--;
					}
				}
			}
		}
	};

void removeDuplicates(std::vector<int>& input){
    
    size_t lastIndex = 0;
    for( size_t i = 1; i < input.size(); ++i){
        if ( input[i] == input[lastIndex]){
            continue;
        }
        
        lastIndex = lastIndex + 1;
        input[lastIndex]=input[i];
    }
    
    input.resize(lastIndex + 1);
    
}

public class Duplicates {
	
	public void moveDistinctFront(int[] a) {
		
		int tail = 0 ;
		for(int i = 1 ; i < a.length ; i++) {
			
			if ( (a[i] != a[i-1]) && (a[i] != a[tail])) {
				
				if (i > tail + 1) {
					++tail ;
					int tmp = a[tail] ;
					a[tail] = a[i] ;
					a[i] = tmp ;
				
				} else if (i == tail +1) {
					++tail ;
				}
			}
							
			
		}
		
		
	}

	public static void main(String args[]) {
		
		int[] a = {1,1,2,2,3,4,4,5,5,5} ;
		
		
		
		Duplicates d = new Duplicates() ;
		d.moveDistinctFront(a);
		
		for(int i : a) {
			System.out.print(i);
			System.out.print(',');
		}
		
		
	}
	
}

C version:

int moveDistinctToTop(int a[], int n)
{
    if(n < 1) return 0;

    int i, next = 1;
    for(i = 1; i < n; ++i){
        if(a[i] == a[i-1]) continue;
        a[next++] = a[i];
    }

    return next;
}

public static int removeDuplicates(int[] a) {
        if(a == null || a.length == 0) {
            return 0;
        }
        int tail = 0;
        for(int i=0;i<a.length;){
            int temp = a[i];
            i++;
            while(i < a.length && a[i] == temp){
                i++;
            }
            if(i == a.length)
                return tail;
            a[++tail] = a[i];
        }
        return tail;
    }

public static void main(String[] args)
{
int[] array = {1,1,2,3,4,4,5};
Set<Integer> set = new LinkedHashSet<>();
for(int a : array)
{
boolean v = set.add(a);
if(!v)
System.out.println(a);
}
}

public static void main(String[] args)
{
int[] array = {1,1,2,3,4,4,5};
Set<Integer> set = new LinkedHashSet<>();
for(int a : array)
{
boolean v = set.add(a);
if(!v)
System.out.println(a);
}
}

public static int[] ArrangeArrea(int[] ar)
        {
            if (ar.Length == 1 || ar.Length == 2)
            {
                return ar;
            }
            for (int i = 1,curr =0; i < ar.Length;)
            {
                if (ar[i] == ar[curr])
                {
                    i++;
                }
                else
                {
                    curr++;
                    int temp = ar[i];
                    ar[i] = ar[curr];
                    ar[curr] = temp;
                    i++;
                }

                
            }
            return ar;
        }

static void refineSort(int a[])
{
int l=a.length;
for(int i=0;i<l-1;i++)
{
if(a[i]==a[i+1])
{
for(int j=i;j<l-1;j++)
{
a[j]=a[j+1];
}

l--;
i--;
}
else
{
System.out.print(a[i]);
}
}
System.out.println(a[l]);
}

This is a variation of dutch-national-flag problem
wikipedia : - Dutch_national_flag_problem

public int removeDuplicates(int[] A) {
        
        int count = 0;
        for(int i=1;i<A.length;i++){
            if(A[i] == A[i-1])
                count++;
            else if(count > 0){
                A[i-count] = A[i];
            }
        }
        return A.length - count;
    }