CareerCup

Compute the expected sum. Compute the actual sum. Difference of the two is the repeated element.

Expected sum could be: n(n+1)/2 if the sequence can be assumed to begin from 1 i.e. 1...n. Else, while iterating over the array to calculate actual sum (which is just the sum of all elements in the array), keep track of min and max. Expected sum (of min...max) can then be calculated as [max(max+1)/2] - [min(min+1)/2] + max.

This is an O(n)/linear time solution. Is there something better?

for(i = 0;i<=n-1;i++)
if (a[i]==a[i+1])
{cout<<a[i];break;}

for n numbers , the sum of first n natural numbers is n(n+1)/2. Calculate this sum , then sum all the elements of the array in one pass , the difference of the 2 sums is the repeated element

If a int is allowed, then bit is the way to go.

a = i = sizeof(arr)/2;
while(a > 0){
a=(a)/2;
if(arr[i] != arr[0]+i)
i -= a;
else
i += a;
}
return arr[i];

If we know a[0]=1 , a[1]=2 .... and so on (elements are sorted), then a binary search can solve the problem

In the case elements are not sorted, the sum method suggested above seems great.

The repeated means one number missing and one is repeated. Time is always linear in solution to such questions. i.e O(N)

I think XOR solution is wrong. Input {3,1,3,4}, it outputs 5 :)

this one is tricky.....
if one number is missing and one number is repeated, we can take the sum of the array.
subtract it from n(n+1)/2. we get the difference between the missing number and the repeated number (x-y). take the product of all the numbers (must result in overflow even for small arrays). then divide this product by the product of numbers from 1 to n. we get the y/x. solve the equation.


if you have the luxury of having an extra array its trivial to solve this one. set a flag in the second array for every number visited in the first array. But we cannot use another array.

So we cannot use an extra array. But most of us fail to realize that we already have an extra array. Look closer. The numbers are of the range 1 to N. We are not using the sign bit. Use the sign bit as the flag. As simple as that.

O(n) (2 traversals)
no extra space.

traverse the list for i= 1st to n elements
{
check for sign of A[abs(A[i])] ;
if positive then
make it negative by A[abs(A[i])]=-A[abs(A[i])];
else // i.e., A[abs(A[i])] is negative
this element (ith element of list) is a repetition
}
Example: A[] = {1,1,2,3,2}
i=1 ; A[abs(A[1])] i.e,A[1] is positive ; so make it negative ;
so list now is {-1,1,2,3,2}

i=2 ; A[abs(A[2])] i.e., A[1] is negative ; so A[i] i.e., A[2] is repetition,
now list is {-1,1,2,3,2}

i=3 ; list now becomes {-1,-1,2,3,2} and A[3] is not repeated
now list becomes {-1,-1,-2,3,2}

i=4 ;
and A[4]=3 is not repeated

i=5 ; we find A[abs(A[i])] = A[2] is negative so A[i]= 2 is a repetition,

This method modifies the original array.

view sourceprint?
#include <stdio.h>
#include <stdlib.h>

void printRepeating(int arr[], int size)
{
int i;

printf("\n The repeating elements are");

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, 3, 2, 2, 1};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;
}

The problem is clear saying that
(1) Numbers are consecutive
(2) One number is repeated
which means the input can be either like
1,2,3,4,4,5,6,7,8
(or)
31,32,33,33,34,,35,36,37
for which the following solution(Space O(1) no extra space, Time = (log n) n is size of input) would work :

#include "stdio.h"
binarysearch(int a[],int n,int low,int high)
{
int mid;
if (low > high) {
printf("Returning unsuccessful!");
return -1;
}
mid = (low + high)/2;
if((a[mid-1] == a[mid])||
(a[mid+1] == a[mid]))
{
printf("The repeating element is %d\n",a[mid]);
return 0;
}
if(a[mid]!=a[a[mid]-a[low]])
{
high = mid - 1;
binarysearch(a,n,low,high);
}
if(a[mid]==a[a[mid]-a[low]])
{
low = mid + 1;
binarysearch(a,n,low,high);
}
}

for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(arr[i]==arr[j])
{
printf("%d",arr[i]);
break;
}

int size = sizeof(a)/sizeof(a[0]);
int repeat = 0;

for(int i=0;i<size-1;++i)
   repeat = repeat ^ (i+1) ^ a[i];

repeat = repeat ^ a[size-1];