CareerCup

void printRepeatedNumer( int * arr, int n )
{
   if( n<=1 ) return;

   int pre = arr[0];
   bool rswitch = false;

   for (int i=1; i<n; ++i)
      if (pre==arr[i])
         if (rswitch == false)
         {  rswitch = true;  PRINT pre; }
         else
            ;
      else { rswitch = false; pre = arr[i]; }
    
    return;
}

If an element is equal to the previous one, then output.
The variable pre in the above code is not necessary.

This one is faster. It does a binary traversal of the sorted array and will prove better when a large array has a lot of duplicates. It does print the duplicates multiple times.

static void findDuplicate(int first,int last, int[] array){
int n=last-first+1;
if(n==2){
if(array[first]==array[last])
System.out.println(array[first]);
return;
} else if(n==1){
return;
} else{
if(n/2 == 1){
if(array[first]==array[first+1])
System.out.println(array[first]);
else if(array[first+1]==array[last])
System.out.println(array[last]);
return;
}else{
if(array[first]==array[last]){
System.out.println(array[first]);
}else{
if(array[n/2]==array[(n/2)-1]){
System.out.println(array[n/2]);
findDuplicate(0,(n/2)-2,array);
findDuplicate(n/2,n-1,array);
}else{
findDuplicate(0,(n/2)-1,array);
findDuplicate(n/2,n-1,array);
}
}
}
}

void repprint(int *arr, int n)
{
int i = 0;
for( i = 0; i < n-1; i++)
{
if(arr[i] == arr[i+1])
{
printf("Val : %d \n", arr[i]);
while((arr[i]!=arr[i+1])&&(i < n-1))
i++;
}
}
}

O(log n) solution..

map<int, int> blist;

 

void count_dup(int* arr, int start, int end)

{

    if(end == 0)

        blist[arr[start]]+=1;

 

    if(start<end) {

        if(arr[start] == arr[end]) {

            blist[arr[end]] += end - start + 1;

            return;

        }

 

        int mid = abs((start+end)/2);

        if(end - start == 2 && arr[start] < arr[mid] && arr[mid] < arr[end]) {

            blist[arr[start]] +=1;

            blist[arr[mid]] +=1;

            blist[arr[end]] +=1;

            return;

        }

 

        if(arr[start] != arr[mid] && start == mid) {

            blist[arr[start]]+=1;

            blist[arr[mid]] += 1;

            return;

        }

 

        if(arr[start] < arr[mid]) {

            count_dup(arr, start, mid);

        } 

        else {

            blist[arr[mid]] += mid - start + 1;

        }

        

        if(arr[mid+1] != arr[end] && mid+1 == end) {

            blist[arr[mid+1]]+=1;

            blist[arr[end]] += 1;

            return;

        }

        

 

        if(arr[mid+1] < arr[end]) {

            count_dup(arr, mid+1, end);

        }

        else {

            blist[arr[end]] += end - mid;

        }

    }

}

 

void main()

{

    int A[] = {1,2,2,3,3,3,4,4,4,5,5,5,5,6,6,6,6,7,7,8,9};

    count_dup(A, 0,20);

 

}

for explanation check here: analgorithmaday <dot> blogspot <dot> com
<slash> 2011<slash> 05 <slash> count-duplicates-in-integer-arraygoogle <dot> html

last=-1;
number=arr[0];
for(int i=1;i<arr.size();i++)
{

if(number==arr[i]&&last!=arr[i]){cout<<arr[i]; last=arr[i];}

else {number=arr[i];}

}

package arraytest;
import java.util.*;


public class Test3
{
	
	
	public static void main(String [] argv)
	{
		int [] numArray = {1,4,3,6,8,9,4,2,3,8 };
		Arrays.sort(numArray); // ascending sort
		
		HashSet<Integer> uniqueNumSet = new HashSet<Integer>();
		
		for (int i=0; i<numArray.length; i++)
		{
			if (uniqueNumSet.contains(numArray[i]))
			{
				System.out.println ("Found duplicate entry: " +numArray[i]);
			}
			else
			{
				System.out.println("First occurence of entry: " + numArray[i]);
				uniqueNumSet.add(numArray[i]);
			}
		}
	}
}

Is it a great idea to use inbuilt functions when asked to solve this problem in an interview? What impression does it creates if you are using inbuilt functions and not using your own functions.

public class DuplicateNumbers
{
public TreeSet<Integer> removeDuplicates(int[] numbers){
TreeSet<Integer> unique = new TreeSet<Integer>();
for(int i=0; i< numbers.length; i++){
unique.add(numbers[i]);
}
return unique;
}
public static void main(String[] args){
DuplicateNumbers dn = new DuplicateNumbers();
int[] numbers={1,1,1,1,1,2,3,4,4,4};
TreeSet<Integer> unique = dn.removeDuplicates(numbers);
Iterator it = unique.iterator();
while(it.hasNext()){
System.out.println("Element is: " + it.next());
}
}
}

Small Correction to the above code....

public class DuplicateNumbers
{
    public TreeSet<Integer> removeDuplicates(int[] numbers){
       TreeSet<Integer> unique = new TreeSet<Integer>();
       for(int i=0; i< numbers.length-1; i++){
           if(numbers[i] == numbers[i+1])
           {
               unique.add(numbers[i]);
           }
       }
        return unique;
    }
    public static void main(String[] args){
          DuplicateNumbers dn = new DuplicateNumbers();
        int[] numbers={1,1,1,1,1,2,3,4,4,4};
         TreeSet<Integer> unique = dn.removeDuplicates(numbers);
        Iterator it = unique.iterator();
        while(it.hasNext()){
            System.out.println("Element is: " + it.next());
        }
    }
}

public class dup_count {

public static int lastVal = Integer.MIN_VALUE;

public static void main(String[] args) {

// Testing with the following test data
int[] a = { 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 9, 9, 9,
10, 10 };

// int[] a = { 1, 2, 3, 4, 5 };

// int[] a = { 3, 3, 3 };

// int[] a = { 1, 1, 3 };

// int[] a = { 1, 1 };

new dup_count().count_dupicates(a, 0, a.length - 1);
}

void count_dupicates(int[] a, int start, int end) {

int mid = (start + end) / 2;

if (end <= start || mid == start && a.length > 2 || mid == end
&& a.length > 2)
return;

// if the mid element == start element, then the start element was
// repeated all
// the way through start to mid location

// a[start] > lastVal: This comparision is just to prevent
// printing the same number again and again

if (a[mid] == a[start] && a[start] > lastVal) {
System.out.println(a[start] + " , ");
lastVal = a[start];
}

else if (a[mid] > a[start]) {
count_dupicates(a, start, mid);
}

if (a[end] == a[mid] && a[end] > lastVal) {
System.out.println(a[end] + " , ");
lastVal = a[end];

return;
}

else if (a[end] > a[mid]) {
count_dupicates(a, mid, end);
}

}
}

Jave code for the above problem statement. Very similar to Binary Search algorithm. Additional ifs had to be put for the case when the array has only 2 and 3 elements.