CareerCup

Find what the sum 1 .. n should sum to with the formula n * (n + 1) / 2 (see 'summation' in wikipedia). Now sum the actual array. If I've read the problem right and there's a single, extra number, the actual sum minus the theoretical sum should give you the extra number.

The best possible answer is this:

As 1..n numbers are there in which one number is repeated, XOR all the numbers with 1..n which cancels out all the numbers from 1..n and gives the repeated number

public int repeated(int[] arr,int n){
	int xor=0;
	for(int i=0;i<arr.length;i++){
		xor^=arr[i];
	}
	for(int i=1;i<=n;i++){
		xor^=i;
	}
	return xor;
}
       
}

Time Complexity: O(n)

You can do this using a HashSet. The boolean add() function can be used to see if an element can be added (ie it is unique). If the function returns false, print out that number.
Time complexity - O(n)
Space complexity - O(1)

#include <stdio.h>
#include <stdlib.h>
 
void printRepeating(int arr[], int size)
{
  int i;
  printf("The repeating elements are: \n");
  for (i = 0; i < size; i++)
  {
    if (arr[abs(arr[i])] >= 0)
      arr[abs(arr[i])] = -arr[abs(arr[i])];
    else
      printf(" %d ", abs(arr[i]));
  }
}
 
int main()
{
  int arr[] = {1, 2, 3, 1, 3, 6, 6};
  int arr_size = sizeof(arr)/sizeof(arr[0]);
  printRepeating(arr, arr_size);
  getchar();
  return 0;
}

Hashmaps:

Scanner scan = new Scanner(System.in);
Map<Integer, Integer> m = new HashMap<Integer, Integer>();
		
int n;
System.out.println("How many numbers?");
n = scan.nextInt();
		
int i = 0, val = 0;
while (i < n)
{
	val = scan.nextInt();
	if (!m.containsKey(val)) m.put(val, 1);
	else
	{
		System.out.println("Double value: " + val);
		return;
	}
	i++;
}

first sort the array then check linearly.
complexity nlogn.

XOR all elements form given set, let say...X
and XOR elements form 1...n,let say..Y
then repeated element is = X(xor)Y
for example set is 1,2,3,4,4
X=1xor2xor3xor4xor4
Y=1xor2xor3xor4
and repeated element is=X(xor)Y=4

I'm confused... if this were a "set" of integers, wouldn't there be no duplicate integers?

suppose your array is :

int[] arr = {1,2,3,10,4,6,7,8,9,10};

then the following code works with time complexity O(n)

Set<Integer> set = new HashSet<Integer>();

for(Integer i : arr) {
if(!set.add(i)) {
System.out.println("This is repeating :: " + i);
}
else set.add(i);
}

Check this out:

int FindDup(int arr[], int n)
{
	for (int i = 1; i <= n; ++i)
	{
		if (arr[i - 1] != i)
		{
			int temp = arr[i - 1];
			arr[i - 1] = arr[arr[i - 1] - 1];
			arr[arr[i - 1] - 1] = temp;
		}
	}

	for (int i = 1; i <= n; ++i)
	{
		if (arr[i - 1] != i)
		{
			return arr[i - 1];
		}
	}

	return 0;
}

0(n)

public static int findDup (int[] a)
	{
		int result =0;
		int xor1 =0;
		int xor2=0;
		
		for(int i=1; i<a.length; i++)   // Xor all the integers from 1 to n-1
		{
			xor1= xor1^i;
		}
		
		for(int i=0; i<a.length; i++)   // Xor all the integers in the array
		{
			xor2 = xor2^a[i];
		}
		
		result = xor1 ^ xor2;
		
		return result;
		
	}

// This was my solution during my Vmware interview.
// where they asked us to remove the repeating elements

removeDuplicates(int arr[], int size, int n){
HashMap<Integer,Integer> hashmap=new HashMap<Integer,Integer>(n);

for(i=0;i<size;i++){
if(hashmap.get(arr[i])==null) hashmap.put(arr[i],1);
else hashmap.put(arr[i], hashmap.get(arr[i]) + 1);
}

leftindex=0;
for(i=0;i<size;i++){
if(hashmap.get(arr[i])>0){
arr[leftindex++]=arr[i];
hashmap.put(arr[i],0); //mark the no. as seen.
}
}
size=leftindex;
}

the question is not clear.Does it mean the repeating number makes the count n+1 or one no. is missing to maintain the count equal to n??

Time complexity O(N)
Space factor is reduced by one-eight as opposed to having a temp arr, which is still O(1).
negative integers and all possible repetitions can be found.

#include<stdio.h>
main()
{
  signed int arr[10] = {34,8,234,5,459,234,-1,99,-1,501};
  int checker=0,i,val;
  for (i=0;i<10;i++)
  {
    val=arr[i];
    if(arr[i]<0) val*=-1;
    if((checker & (1<<val))> 0)
      printf("arr[%d] = %d is repeated\n",i,arr[i]);
    checker |= (1<<val);
  }
}

Put the numbers in an array in ascending order
Sum of all numbers = x
number of numbers = n
Now the position of repeated number from higher end = (n*(n+1)/2) - x
For example : 1,2,2,3,4
Position from higher end P = 15 - 12 = 3
so repeated number is in 3rd position from higher end so answer is 2
or example : 1,2,3,4,4
Position from higher end P = 15 - 14 = 1
so repeated number is in 1st position from higher end so answer is 4

The question is not clear to me.
I can deduce 2 scenarios from the question:
Case 1: One number is repeated and the there are 'n+1' numbers.
Case 2: One number is repeated and another number is missing. So, there are 'n' numbers.

-----------------------

Case 1 Solution:

Calculate sum of available 'n+1' numbers. Let's say it's 's1' .
Calculate sum of (1, 2, ..., n) using formula n*(n+1)/2. Let's say it's 's' .

So, repeated number is (s1 - s)

Time complexity: O(n) i.e. time needed to traverse the array to calculate the sum.

-----------------------

Case 2 Solution:

Let's say that the missing number is 'a' and repeated number is 'b' .

Calculate sum of available 'n' numbers. Let's say it's 's1' .
Calculate sum of (1, 2, ..., n) using formula n*(n+1)/2. Let's say it's 's' .
If 's' is bigger than 's1', then (a - b) = (s - s1), otherwise (b - a) = (s1 - s) .

Calculate sum of squares of available 'n' numbers. Let's say it's 't1' .
Calculate sum of (1^2, 2^2, ..., n^2) using formula n*(n+1)*(2*n+1)/6. Let's say it's 't' .
If 't' is bigger than 't1', then (a^2 - b^2) = (t - t1), otherwise (b^2 - a^2) = (t1 - t) .

Now, (a^2 - b^2) = (a+b)*(a-b)

Hence, solve the two equations to get the missing number and repeated number.

Time complexity: O(n) i.e. time needed to traverse the array to calculate the sums.