CareerCup

time complexity is more , is it not possible with xor tricks?

Simple answer: no, it's not possible with XOR tricks.

Xor tricks work when you know some range i.e array size is n+1 and the numbers are in between 1 to n all like that. otherwise if the random number is there then you wont be able to find any answer using xor.

package com.careercup;

import java.util.HashSet;

public class FindDuplicateUsingMaps {
	
	public static HashSet<Integer> getDuplicates(int[] givenArray)
	{
		HashSet<Integer> v=new HashSet<Integer>();
	    HashSet<Integer> hs=new HashSet<Integer>();
	    
	    for(int a: givenArray)
	    {
	    	if(!hs.add(a))
	    	{
	    		v.add(a);
	    	}
	    }
	    return v;
	
	}
	
	public static void main(String[] args)
	{
		int[] givenArray={0,1,1,2,4,1,1,1};
		HashSet<Integer> v= getDuplicates(givenArray);
		for(int duplicates: v)
		{
			System.out.println(duplicates);
		}
	}
}

Time complexity is: Theta(n)
Space complexity: O(n)

no range is given , array can contain random number.

then sorting and comparing is all i can think of. Hopefully someone here will come up with a better solution.

thanks
if range is given then we can xor the array element with the index and get the answer .But here i have one doubt
if a[5]={0,1,1,2,4} range is (0-4) then how we find out the repeated number.

if suppose the range is (0-4) like you are saying, then we create an integer array of size 5, call it finalArray. Initialize the array to 0s for each index. Now iterate through the given array. First number is 0. Mark finalArray[0]=1, similarly go making the 0s into 1s. When we reach a point when when the finalArray[index] value is already 1, then that is the repeated number.

and space complexity of this approach is "n".
correct me if i m wrong.

and one more thing how can we do this problem using xor .

if you mean 'n' when n is the size of the given array, then no. The array size may be 300. But the given range may be [0-30]. So the size of the binary array we make will be only 31. Actually this approach is best when the array is a set of characters. We can make an array of size 26(number of english alphabets). However for small given rages it can be effectively used. If the range is from 1 to 1 million then using this method would be useless.

package com.careercup;

public class FindDuplicates {

	public static int[] getDuplicates(int[] givenArray, int range)
	{
		int i=0;
		int[] binaryArray=new int[range+1];
		int[] arrayOfDuplicates= new int[range+1];
		
		for(int b:givenArray)
		{
			if(binaryArray[b]==1)
			{
				arrayOfDuplicates[i]=b;
				i++;
				binaryArray[b]=2;
			}
			else if(binaryArray[b]==0)
			{
				binaryArray[b]=1;
			}
		}
		int[] arrayOfDuplicates1=new int[i];
		for(int m=0;m<i;m++)
		{
			arrayOfDuplicates1[m]=arrayOfDuplicates[m];
		}
		
		return arrayOfDuplicates1;
	}
	
	public static void main(String[] args)
	{
		int[] givenArray={0,1,1,2,4};
		int range=4;
		int[] arrayOfDuplicates= getDuplicates(givenArray,range);
		for(int duplicates: arrayOfDuplicates)
		{
			System.out.println(duplicates);
		}
	}
}

this code is for only when the range is given.

Time complexity: Theta(n)
Space complexity: O(1)

How can be the time complexity equals to o(n).
first you find out the maximum number i.e access the complete array,then you again fill the array with numbers , and then search the repeated number.
i guess in this case the time complexity is greater than o(n).

Hmm, I think this may work not so efficiently when the given array is like {1, 65535}, this will make the count array very sparse. But if we require O(n) time complexity, I think there are no better ways, just to sacrifice the space. We can use bit array to minimize the sacrifice.

suppose 'k' is too large, this will cause a huge space complexity. The array might be something like {1,1,1crore}. We should use this only when k is a small number. Also we are forgetting, there maybe be negative integers too. So when the given range is [0-small_number] then we can use the approach u are mentioning.

Each step is O(n), and they are independence steps， so in all is 3*O(n)（maybe，the prefix is a constant）, still O(n). It will not become O(nlgn) or O(n^2).

If there are negative integers, we should use hashmap instead.

@onpduo: your approach makes no sense to me. Maybe I'm not understanding you.

So it is a binary search tree? When you insert a number into this tree, you need to search from root, just a little bit like insertion sort, thus the time complexity is larger than O(n).

it depends on input...
for the best case:
while inserting 2nd and 3rd element it is O(1)
while inserting 4th to 7th element it is O(2)
so its just O(lg n) .. it is not O(n)

average case and worst case: O(nlgn)

in the worst case: for 2nd element it has to traverse only 1 element
for 3rd element , to traverse only 2 elements
we cant say this as O(n^2)

This is a bad solution because if you're going to have O(NlogN) complexity, you might as well do something like sort 2 arrays and then compare them sequentially. This will have a much lower constant factor and will use less space, by a constant factor.

wastage of space is high.

for the input {1,1000}
bitSet.length() = 1001
bitSet.size() = 1024

Bitset's only appropriate when the range of values is small.

Oops, I meant

if(!visited[element])

but an array of size 2^32 is a lot of space. Imagine the given array is {1,2} then look at the space wastage.

It takes a long time to loop over an array of size 2^32. And what if they're 64 bit integers?