Finding duplicate element in array in O(n)

//Code to check the duplicacy of numbers in a array using negation technique
//Constraint is numbers allowed in array of size n are from 0 to n-1
//Checking the duplicacy in O(n) time complexity and constant space
package checkduplicate;

import java.util.Scanner;

public class CheckDuplicate{

public static void main(String arg[])
{
int a[]=new int[10];
Scanner sc=new Scanner(System.in);
System.out.println(“Enter the numbers”);
for(int i=0;i<a.length;i++)
a[i]=sc.nextInt();
System.out.println(“Duplicacy in the number entered”+check(a)) ;

}

static boolean check(int a[])
{
boolean ctZero=false;
for(int i=0;i<a.length;i++)
if(a[Math.abs(a[i])]<0)
return true;
else if (a[Math.abs(a[i])]>0)
{a[Math.abs(a[i])]=a[a[i]]*-1;}
else
if(!ctZero)
ctZero=true;
else
return true;

return false;
}
}

Leave a Reply

Your email address will not be published. Required fields are marked *