CareerCup

package com.algorithm.amazon;

import java.util.Arrays;

public class DuplicateNumbers {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = { 1, 2, 2, 2, 2, 4, 3, 2, 5, 6 };
		Arrays.sort(arr);
		for (int i = 1; i < arr.length; i++) {
			if (arr[i] == arr[i - 1]) {
				System.out.println(arr[i]);
				return;
			}
		}

	}

}

Arrays.sort(a);
      System.out.println((a[0] == a[4]) ? a[0] : a[5]);

This works assuming Arrays.sort(a) is considered as one step.

can you define two steps?

Let us say the array is A.

The good hint to keep in mind is that - out of 10, 5 elements have same value, so if we sort the array these 5 elements can be from any index to that index+4 in the sorted array. But elements in A[4] or A[5] will be one of them for sure. We just need to discard one out of A[4] and A[5].

steps:
1) Sort the array
2) Compare element number 4 and 5 in the sorted array, if a[3] ==a[4] then print [4], else print a[5].

let me know if this is wrong....

step1 short the array
for(int i=0;i<n-1;i++)
{
if(arr[i]==arr[i+1])
{
found;
break;
}
}

There can be three cases:
1. {1,2,3,4,5,7,1,1,1,1} // 1 is the answer
2. {1,2,3,5,9,10,3,3,3,3} // 3 is the answer
3. {1,2,9,9,9,6,7,9,9,4} // 9 is the answer

If we use quick select for the 5th position (5 is half of 10)
Array will be sorted like
1. {1,1,1,1,1, other numbers greater than 1}
2. {numbers less than 3, 3,3,3,3,3, numbers greater than 3}
3. {1,2,7,6,8,9,9,9,9,9}

In any case, you can do quick select for 5th index number.
Then, for case.1 and case.2, you can simply check that there are 5 numbers of this value.
In case.3, all numbers from index.5 to index.9 will be equal.

Codes:

public static int findFiveTimesRepetiveNum(int[] arr) {
	assert(arr != null || arr.length == 10);
	int selectedNum = arr[quickIndexSelect(arr, 5)];
	int count = 0;
	for (int i : arr) {
	  if (i == selectedNum) {
		count++;
	  } 
	}

	if (count == 5) return selectedNum; // It covers case.1 and case.2
	for (int j = 5; j < arr.length; j++) {
	  // In case.2, we need to figrue out all numbers from index 5~inedx.9 are equal
	  if (arr[j] != arr[5]) {
		return -1;
	  }
	}
	return arr[5];
  }
  
  public static void main (String[] args) {
	int[] case1 = new int[]{1,2,3,4,5,7,1,1,1,1};
	int[] case2 = new int[]{1,2,3,5,9,10,3,3,3,3};
	int[] case3 = new int[]{1,2,9,9,9,6,7,9,9,4};
	
	print("Expect 1: " + findFiveTimesRepetiveNum(case1));
	print("Expect 3: " + findFiveTimesRepetiveNum(case2));
	print("Expect 9: " + findFiveTimesRepetiveNum(case3));
	
	int[] canNotFound = new int[]{1,2,3,4,5,6,7,8,9,10};
	print("Expect -1(Can not found): " + findFiveTimesRepetiveNum(canNotFound));

assumed array index starts from 1 - 10 & array is sorted. if array is NOT sorted then solution is not possible 

if(a[5] == a[6])
	return a[5];	// a[5] & a[6] are part of duplicate sequence
else if(a[4] == a[5])
	return a[5];	// a[1] to a[5] are duplicates
else
	return a[6];	// a[6] to a[10] are duplicates

The obvious idea is to use xor.

In first step, xor every consequitive element and you found the element, if the xor is zero.

There is a problem when same elements are alternate:
1 6 2 6 3 6 4 6 5 6

In this case, xor with next to next element, this will find the element in this special case.

The complexity is O(n)

Step 1: Sort the array.
Step 2: Find the difference between the next index element and the current index element. If the difference is 0, then the number either at current or next index is the repeating number.

Example:

public static void findRepeatingNumber() {
	int[] intArray = new int[10];
	intArray[0] = 27;
	intArray[1] = 91;
	intArray[2] = 84;
	intArray[3] = 71;
	intArray[4] = 65;
	intArray[5] = 71;
	intArray[6] = 31;
	intArray[7] = 71;
	intArray[8] = 71;
	intArray[9] = 71;
	System.out.println("Original Array: " + Arrays.toString(intArray));
	Arrays.sort(intArray);
	System.out.println("Sorted Array: " + Arrays.toString(intArray));
	int diff = 0;
		for (int i = 0; i < 9; i++) {
		diff = intArray[i + 1] - intArray[i];
		if (diff == 0) {
			System.out.println("Repeating number: " + intArray[i]);
			break;
		}
	}
}

if there is no restriction on extra space, then have a HashSet and add the values. When ever you encounter a duplicate value, return it.

Step 1: Calculate sum1 and sum2, where sum1 = all the elements in the array and sum2 is the sum of those 6 six unique numbers.

Step2 : Calculate the repeated number as: repeated_number = (sum1 - sum2) / 4;

its a finite array,arr[] of length 10
so start by doing a simple algorithm
add i,x element
where x= 10-i
& i = first
add arr[i]+arr[x]=y
then calculate z=y-arr[x]
& do the above step till i=4
if z is common for any, then you got the duplicate entity
if no common value is found, the arr[5], element at index 5 is the duplicate entity :)

The solution below is particularly tuned for just this problem (not generic), but serves the purpose for the mentioned problem. The solution i think is basically O(n-1).

public class TwoStep {

	public static void main(String[] args) {
		Integer[] numList = {5,2,1,5,3,4,5,6,5,5};
		
		//we do numList.length-1 so that we don't get the array out of bounds exception when accessing the value at i+1
		for(int i=0; i < numList.length-1 ; i++){	
			//We check if value at i == i+1 
			//or
			// if i-1 >=0 and i-1 == i+1
			//then i+1 should be the matched value
			//since we know there is only one value that is going to be repeated
			//we can break the loop at this point and print out the output
			if((numList[i] == numList[i+1]) || (i-1 >= 0 && numList[i+1] == numList[i-1])){				
				System.out.println(numList[i+1]); 
				break;
			}
		}
	}
}

Friends I have designed this algorithm which takes constant time and whatsoever may be the position of the duplicate elements one of the conditions specified in my algo will always satisfy. But please do correct me if any of the cases which u have tried proves me wrong..

Here 's my code.
i- first elemnt
J-last element
Mid = (i+j/2)

if(a[i]==a[i+1])
return a[i]

Elseif(a[j]==a[j-1])
Return a[j]

elseif(a[i]==a[j])
return a[i]

elseif(a[mid]==a[mid-1] ||a[mid]==a[mid+1])
return a[mid]

'two steps' means that scan the array twice？If it is, we can do like this:
For first time scan, every time we see two different number, we 'delete' them from the array. At last, there is two cases: (a)only one same number left, so it is the number repeated for 5 times(b)there are two different numbers left, named A and B, we choose one of them(e.g. A) and scan the array again, count the times it repeated. If count == 5, A is the number we want, If not, B is the result. Noted that we don't need to delete number really, we only use a parameter to count different numbers we see when we scan, If it is 2, we reset count = 0.

step 1: sort array in ascending order
step 2:
compare a[4] against a[5],
if a[4] == a[5] return a[4]
else
#two possible outcome
#either the 5 repeated numbers are in the first 5 slots of the array or in the last 5
if a[3] == a[4] return a[4]
else
return a[5]

public static int findDuplicate(int a[]){
		
		if(a.length <= 0)
			return -1;
		
		int dupVal = a[0];
		int count = 1;
		
		for(int i = 1; i < a.length; i++){
			if(a[i] == dupVal){
				count ++;
				if(count == 5)
					break;
			} else {
				count --;
			}
			
			if(count <= 0){
				count = 1;
				dupVal = a[i];
			}
		}
		
		return dupVal;
	}

Since there's nothing mentioned about memory, why not have 6 pointers and compare their values. Since there are 5 unique numbers, when you take 6 pointers, the repeating number will be present twice.

Since there's nothing mentioned about memory, why not have 6 pointers and compare their values. Since there are 5 unique numbers, when you take 6 pointers, the repeating number will be present twice.

Solving this in 2 steps:

Consider a hashset: hs, uniqueSum which is sum of all unique numbers initialized to 0 and a totalSum which is a sum of all numbers in the array.

Step 1:

foreach x in array:
    if (hs.add(x) is true): // note: Java's hashset returns true if element is not already present in it
        uniqueSum += x;
    totalSum += x;

Step 2:

duplicateNumber = (totalSum - uniqueSum) / 4

So e.g. array = {1,2,3,4,5,6,5,5,5,5}
uniqueSum = 20; totalSum = 40
duplicateNumber = 5

Does the initial array is known?

If yes, sum the initial array and then sum the modified array.

Get difference of both the summations and divide the result by 4.

---all the cases except will be covered in while loop ..except when the repeated number is in alternative position...
while (i<n)
{
if (a[i] =a[i+1])
return a[i];
}
---will cover the case when array will be like ...121314... or 213141...
if(a[0] == a[2])
return a[0];
else
return a[1];

take two pointers , point one at first and one at third. keep on moving one step each till those two point to same value. .
ex: 1a2a3a4a5a .. these two meet at a's which are after 1 , and after 2 .. (in one move)
12aa3a4a5a .. these two meet a's which are before 3 and after 3 ..(3 steps)
123aaa4a5a .. two meet which are after 4 and seond a after 3 ...
1234aaaa5a .. 12345aaaaa .. straight