CareerCup

There are only two good solutions for this problem.

1. Using hashtable as @zbesst and @coding.arya suggested, which is O(n) time and space
2.Sorting solution which is O(n lg n) time and O(1) space.

I saw someone -1'd the posts of @zbesst and @coding.arya. When people do that, they should at least have the courtesy to write the reason. I'll +1 you guys.

1) Use a HashSet or equivalently

2) Use a HashTable that maps a[i] -> # of occurrences, then print all keys.

Both are O(n) time and space.

1. Use a map and insert all the elements one by one avoiding duplicate. 0(nlogn)
2. Use HashTable.

if range of integers is given and is small make a count of every element ,
else sort them using radix sort in linear time and remove duplicates

public class RepeatString {
public static void main(String[] args) {
String str = "this is neeraj and neeraj is a good boy";
String str1[] = str.split(" ");
Set st =new HashSet();
for (String s : str1)
{
if(!st.add(s))
{
System.out.println("repeated word is :" +s);
}
}

}
}

Create a binary search tree, and each time when you find a duplicate element while inserting a new element, reject it.
Time Complexity O(nlogn)

Questions you ought to ask for clarification:

1.) Is the array sorted?
2.) Does the array order need to be maintained?


A.) If it's sorted, you can do it in O(n) with no additional data structures.

B.) If the order does not need to be maintained, then I would argue to sort the array O(n log n), space O(n), and then perform the O(n) search. However both these techniques would require you to delete from an array, which is O(n).

C.) If order doesn't matter, then the "simplest" thing to do would be to add them to a tree that doesn't allow repeats (like a set), insertion O(log n), and then traverse the tree to write out the results into the existing array. Space complexity goes up to O(n), but you stay at O(log n) + O(n)

public void removeduplicates(int[] array)
        {
            int i, j, new_length = 1;

            for (i = 1; i < array.Length; i++)
            {

                for (j = 0; j < new_length; j++)
                {

                    if (array[i] == array[j])
                        break;
                }

                /* if none of the values in index[0..j] of array is not same as array[i],
                   then copy the current value to corresponding new position in array */

                if (j == new_length)
                    array[new_length++] = array[i];
            }


            for (i = 0; i < new_length; i++)
            {
                Console.WriteLine(array[i]);
            }
        }

void main()
{
int n,*a,i,j,k;
printf("enter the size of the array:\n");
scanf("%d",&n);
a=(int*)malloc(n*sizeof(int));
printf("enter the elements:\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]==a[j])
{
for(k=j;k<n;k++)
a[k]=a[k+1];
n--;
j--;
}
}
}
for(i=0;i<n;i++)
printf(" %d",a[i]);
}

first, you'd have a set which holds the integers.
second, you'd have to put the integers of the array into the set.
third, you can have the numbers which is unique.

Traverse the array once. While traversing, keep track of count of all elements in the array using a temp array count[] of size n, when you see an element whose count is already set, then that element is duplicate :
if(count[arr[i]]==1) then that element is duplicate...