CareerCup

public int findRepeatingNumber(int[] array, int n) {
		int sumOfSequence = (n*(n+1))/2;

		for (int element : array) {
			sumOfSequence -= element;
		}

		return Math.abs(sumOfSequence);
	}

public static int repeatedNumber(final List<Integer> a) {
		if (a.size() > 1) {
			int slow = a.get(0);
			int fast = a.get(a.get(0));
			while (slow != fast) {
				slow = a.get(slow);
				fast = a.get(a.get(fast));
			}

			fast = 0;
			while (fast != slow) {
				slow = a.get(slow);
				fast = a.get(fast);
			}
			return slow;
		}

		return -1;

}

int ans = -1;
    if (A.size() > 1) {
		int slow = A[0];
		int fast = A[A[0]];
		while (slow != fast) {
			slow = A[slow];
			fast = A[A[fast]];
		}
 
		fast = 0;
		while (fast != slow) {
			slow = A[slow];
			fast = A[fast];
		}
		ans = slow;
	}
    return ans;

SumoftheStream - (n(N+1)/2)

def foo(n):
	for i in range(0,len(n)):
		if(n[abs(n[i])]>=0):
			n[abs(n[i])] = -n[abs(n[i])]
		else:
			print abs(n[i])

There are 3 restrictions in the question and above 3 solutions which uses arrays fail to satisfy at least one of the restriction:

1. The additional space complexity should be less than O(n)
--> Means we can not use array as that will require O(n) space to hold all elements

2. The input is coming as a stream
--> This means you can not use array again as you dont have all the data at the same time. You can read each input and add it to the array but that will violate restriction 1.

3. Time complexity is linear. O(n)
--> So we can not run loop inside a loop or go back and forth in the array.

Solution:
=======
Since the input is coming as a stream of integer, the logical solution is to create a binary search tree (BST) as the integers come in.

For each input, insert the integer in BST.
If you find the integer already present you found the repeating element which is the answer.
If integer is not present in the BST, add that integer.

Space complexity < O(N)
This approach would take less than the max number of elements in the input as in the worst case last element will match the existing element and we wont have to store that last element

Time complexity is O(N)
Worst case time complexity for searching a number. 
As pointed out in the comment, the time complexity for constructing BST is O(nlogn). But the question asks for linear time complexity for searching a number which is O(n)

public int repeatingNumber(int[] array, int n) {
	int sumOfSequence = (n*(n+1))/2;

	for (int element : array) {
		sumOfSequence -= element;
	}

	return Math.abs(sumOfSequence);
}

python implementation:

arr = [1,2,3,4,2,6,5,7,9,0,8]

temp={}
for i in arr:
  if not temp.has_key(i):
    temp[i]=1
  else:
    print i
    break

Let
Array a = {1,2,3,4,5,5}
n = 5
Find the arithmetic sum of n integers n=5 means arithmetic sum=15
Next sum all the elements in array sum=20

missing number = sum - arithmetic sum = 20 - 15 = 5

public class Test {
	
	public static int findRepeat(int[] a) {
		int n = a.length-1;
		int r1 = n*(n+1)/2;
		int sum=0;
		for(int i=0;i<=n;i++) {
			sum+=a[i];
		}
		
		return sum-r1;
	}

	public static void main(String[] args) {
		int[] a = {1,2,3,4,5,5};
		System.out.println(findRepeat(a));

	}

}

will incoming stream be a structured so as to fit in binary search tree.that is if incoming stream is 1,2,3,4,5.?how will we build bst without looking all the elements.we can build BST out of sorted int array(but again this violates your not storing all the stuff in the element).
I think the best would be to do arraylist/set to store the stuff.that is keep on adding in arraylist,untill you hit same element again.(if(set.contains(incoming element) do a break and come out of the loop in this way you won;t have stored all the elements and and search is also linear,unless specified way the data is coming on stream,I think only viable solution is to use arraylist or set to do a contains/add method and break if it return true.

import java.util.ArrayList;
import java.util.Random;

public class FindDuplicates {

public static void main(String[] args) {
// TODO Auto-generated method stub

Random random = new Random();
ArrayList<Integer> arrayList = new ArrayList<>();
int randomnumber = 0;
for (int i = 0; i < 1000; i++) {
randomnumber = random.nextInt(10);
if (arrayList.contains(randomnumber)) {
break;
}
}

System.out.println(randomnumber +">>>>>>>>>>>>" +"has already been processed ");

}

}

package com.amazon.set1;





public class LinearNumberExample {
	public static void main(String[] args) {
		int[] array = { 1,2,3, 4, 5, 5 };
		//A.P to find the actual final element which is to be present.
		int finalTerm = 1 + (array.length - 1) * 1;
		//A.P to find the sum which is to be
		int sum = array.length * (1 + finalTerm) / 2;
		// As we iterate, we get to the difference in between the actual and the hypothetical.
		for (int i = 0; i < array.length; i++) {
			sum -= array[i];
		}
		if(sum==0)
		{
			System.out.println("No Duplicates");
			return;
		}
		//By subtracting, we get the index of where the duplicate lies.
		System.out.println(array[array.length-Math.abs(sum)]);
	}
}

package com.amazon.set1;





public class LinearNumberExample {
	public static void main(String[] args) {
		int[] array = { 1,2,3, 4, 5, 5 };
		//A.P to find the actual final element which is to be present.
		int finalTerm = 1 + (array.length - 1) * 1;
		//A.P to find the sum which is to be
		int sum = array.length * (1 + finalTerm) / 2;
		// As we iterate, we get to the difference in between the actual and the hypothetical.
		for (int i = 0; i < array.length; i++) {
			sum -= array[i];
		}
		if(sum==0)
		{
			System.out.println("No Duplicates");
			return;
		}
		//By subtracting, we get the index of where the duplicate lies.
		System.out.println(array[array.length-Math.abs(sum)]);
	}
}

public class LinearNumberExample {
public static void main(String[] args) {
int[] array = { 1,2,3, 4, 5, 5 };
//A.P to find the actual final element which is to be present.
int finalTerm = 1 + (array.length - 1) * 1;
//A.P to find the sum which is to be
int sum = array.length * (1 + finalTerm) / 2;
// As we iterate, we get to the difference in between the actual and the hypothetical.
for (int i = 0; i < array.length; i++) {
sum -= array[i];
}
if(sum==0)
{
System.out.println("No Duplicates");
return;
}
//By subtracting, we get the index of where the duplicate lies.
System.out.println(array[array.length-Math.abs(sum)]);
}
}

public class RepeatedInteger {

    public static void main(String[] args) {
        int[] arr = {2 ,1, 3,2,4};
        int n=5;

        int result=0;
        for (int i=0; i<n;i++){
            result^=arr[i];
        }

        for (int i=1; i<n; i++){
            result^=i;
        }

        System.out.println(result);
    }
}

In the problem, it is not mentioned that the number will repeat only once, your solution will fail for 3 3 3 3 3
kindly correct me if I'm heading in the wrong direction.
Solution that I found:
{{
int repeatedNumber(const vector<int> &V) {
if (V.size() <= 1) return -1;
int valueRange = V.size() - 1;
int range = sqrt(valueRange);
if (range * range < valueRange) range++;
int count[range + 1];
memset(count, 0, sizeof(count));

for (int i = 0; i < V.size(); i++) {
count[(V[i] - 1) / range]++;
}

int repeatingRange = -1;
int numRanges = ((valueRange - 1) / range) + 1;
for (int i = 0; i < numRanges && repeatingRange == -1; i++) {
if (i < numRanges - 1 || valueRange % range == 0) {
if (count[i] > range) repeatingRange = i;
} else {
if (count[i] > valueRange % range) repeatingRange = i;
}
}
if (repeatingRange == -1) return -1;
memset(count, 0, sizeof(count));
for (int i = 0; i < V.size(); i++) {
if ((V[i] - 1) / range == repeatingRange) count[(V[i] - 1) % range]++;
}
for (int i = 0; i < range; i++) {
if (count[i] > 1) {
return repeatingRange * range + i + 1;
}
}
return -1;
}
}}

In the problem, it is not mentioned that the number will repeat only once, your solution will fail for 3 3 3 3 3
kindly correct me if I'm heading in the wrong direction.
Solution that I found:
{{int repeatedNumber(const vector<int> &V) {
if (V.size() <= 1) return -1;
int valueRange = V.size() - 1;
int range = sqrt(valueRange);
if (range * range < valueRange) range++;
int count[range + 1];
memset(count, 0, sizeof(count));

for (int i = 0; i < V.size(); i++) {
count[(V[i] - 1) / range]++;
}

int repeatingRange = -1;
int numRanges = ((valueRange - 1) / range) + 1;
for (int i = 0; i < numRanges && repeatingRange == -1; i++) {
if (i < numRanges - 1 || valueRange % range == 0) {
if (count[i] > range) repeatingRange = i;
} else {
if (count[i] > valueRange % range) repeatingRange = i;
}
}
if (repeatingRange == -1) return -1;
memset(count, 0, sizeof(count));
for (int i = 0; i < V.size(); i++) {
if ((V[i] - 1) / range == repeatingRange) count[(V[i] - 1) % range]++;
}
for (int i = 0; i < range; i++) {
if (count[i] > 1) {
return repeatingRange * range + i + 1;
}
}
return -1;
}}}

int ans = -1;
    if (A.size() > 1) {
		int slow = A[0];
		int fast = A[A[0]];
		while (slow != fast) {
			slow = A[slow];
			fast = A[A[fast]];
		}
 
		fast = 0;
		while (fast != slow) {
			slow = A[slow];
			fast = A[fast];
		}
		ans = slow;
	}
    return ans;

Sab bhadwe

int find_rep(int arr[],int n)
{
	for(int i=0;i<n;++i)
	{
		if(arr[abs(arr[i])]<0)
			return abs(arr[i]);
		else
		{
			arr[abs(arr[i])] = -arr[abs(arr[i])];
		}
	}
	return -1;
}

public class FindRep {
    
   public static void main(String[] args){
    
       int[] arr = {1,3,1,4,5,6,7,8,2,9};
       FindRep rep = new FindRep();
       System.out.println(rep.FindRepNum(arr));
       
   }
   
   public int FindRepNum(int[] arr1){
       
       HashSet myset = new HashSet();
       
       for(int i: arr1){
           
           if(myset.contains(i)){
               return i;
           }else{
               myset.add(i);
           }
       }
      return -1; 
   }
    
}

package com.amazon.set1;





public class LinearNumberExample {
public static void main(String[] args) {
int[] array = { 1,2,3, 4, 5, 5 };
//A.P to find the actual final element which is to be present.
int finalTerm = 1 + (array.length - 1) * 1;
//A.P to find the sum which is to be
int sum = array.length * (1 + finalTerm) / 2;
// As we iterate, we get to the difference in between the actual and the hypothetical.
for (int i = 0; i < array.length; i++) {
sum -= array[i];
}
if(sum==0)
{
System.out.println("No Duplicates");
return;
}
//By subtracting, we get the index of where the duplicate lies.
System.out.println(array[array.length-Math.abs(sum)]);
}
}

You can use xor.

public int findRep(int[] arr)
{
	if(arr==null ||arr.length==0)
	{
		return -1;
	}
	int xor=arr[0];
	int result=-1;
	for(int i=0;i<arr.length;i++)
	{
		xor^=arr[i];
		if(xor==0)
		{
			result=arr[i];
			break;
		}
	}
	return result;
}