CareerCup

simple, let the input be 1,4,3,2,4
4 is repeated, 5 is missing, let repeated number be x1 and missing number be x2

arithmetic progression
n(n+1)/2 - x2 + x1 = summation of all the numbers

5(5+1)/2 - x2 + x1 = 14
15 - x2 + x1 = 14
x2-x1 = 1 -------> equation 1

find the product
(n! * x1)/x2 = product of all the numbers

((1*2*3*4*5) * x1) / x2 = 1*2*3*4*4
(120 * x1) / x2 = 96
120 * x1 = 96 * x2
x1 = (96 * x2) / 120 -------------> equation 2

substitute x1 in equation 1

x2 - ((96*x2) / 120) = 1

120 * x2 - 96 * x2 = 120

24 * x2 = 120

x2 = 5

substitute x2 in equation 1

5 - x1 = 1

x1 = 4

hence proved :-)

This is a very simple solution in C# without that math shit.

static void GetMissingNum()
        {
            int[] a = { 5, 4, 4, 2, 1};
            int[] b = new int[a.Length];

            for (int i = 0; i < a.Length; i++)
                b[a[i] - 1]++;
            for (int i = 0; i < b.Length; i++)
            {
                if (b[i] == 0)
                    Console.WriteLine("Missing: {0}", i + 1);
                else if (b[i] > 1)
                    Console.WriteLine("Repeated: {0}", i + 1);
            }              
        }

#include<stdio.h>
int main()
{
    int n,i;
    scanf("%d",&n);
    int arr[n];
    for(i=0;i<n;i++)
        scanf("%d",&arr[i]);
   int sum_of_digit=0;
   int sum_of_sqdigit=0;
    for(i=0;i<n;i++)
    {
        sum_of_digit+=arr[i];
        sum_of_sqdigit+=arr[i]*arr[i];
    }
    int sum_of_digit1=(n*(n+1))/2;
    int sum_of_sqdigit1=(n*(n+1)*(2*n+1))/6;
    int repeat_value=((sum_of_sqdigit-sum_of_sqdigit1)/(sum_of_digit-sum_of_digit1)+(sum_of_digit-sum_of_digit1))/2;
    int miss_value=((sum_of_sqdigit-sum_of_sqdigit1)/(sum_of_digit-sum_of_digit1)-(sum_of_digit-sum_of_digit1))/2;
    printf("epeated valu=%d\nmiss value=%d",repeat_value,miss_value);
    return 0;
}

int main(){
	int a[] = {1,3,4,5,4};
	for(int i=0;i<5;i++){
		if(a[i] != i+1){
			int temp = a[i];
			a[i] = a[a[i] - 1];
			a[temp-1] = temp;
		}
	}
for(int i = 0; i < 5; i++)
	if(a[i] != i+1)
		cout << "Number missing is" << i+1
				<< endl;
}

simple solution ..

just to internal hushing ..

2 3 3 6 4 1
1 2 3 4 5 6

swap(1,2)

3 2 3 6 4 1
1 2 3 4 5 6

swap(1,3) , you notice its a cycle u find repeated no. 3 and may be missing no. 1 save it then go further

swap(4,6)

3 2 3 1 4 6
1 2 3 4 5 6

swap(1,4)
1 2 3 3 4 6
1 2 3 4 5 6
now again cycle update missing no. 4 and go further

swap(4,5)

1 2 3 4 3 6
1 2 3 4 5 6

again cycle update missing no. 5 go further

at the end u have missing no. and repeated no.

C# Solution

public void FindMissingAndRepeatedNum(Int32[] arr, int N, out int repeatedNum, out int missingNum)
      {
         /*Array Ranges from 1 to N*/
         Int32 SumOf1ToN = (N * (N + 1)) / 2; /*All Numbers 1 to N without repeat or missing*/

         Int32 ProductOf1ToN = 1;
         /*N! - Product of ALL 1 to N without repeat and missing*/
         for (int i = 1; i <= N; i++)
            ProductOf1ToN *= i;

         /*N! / missing_number == (ProductOfArray / repeated_number) * missing_number*/
         /*For EX: Array is [1,2,3,4,6,2] 
          * ANS: missing number is 5 and repeated is 2, range (N)  =6 
          * Suppose X = repeated Number, Y = missing numbers
          * N! = 6! = (1*2*3*4*5*6) = (1*2*3*4*X*6)
          * Product of Array = (1*2*3*4*6*2) = (1*Y*3*4*6*Y)
          * Thus: N! = (1*2*3*4*5*6) = (1*2*3*4*5*6*2)/5 = (1*2*3*4*6*2) = Product OfArray
          * i.e (N! * X(repeated number)) / Y(missing number)  == Product Of Array
          * (N! * X)/ Y = P; 
          * Y = (N!/P) * X == (720/288)*x = (5/2)X
          * 
          * SUM OF ARRAY ELEMENTS - SUM OF 1 to N Numbers  = Sum of Repeated number - Sum of Missing Number 
          * Sum Of Array Elements = 1+2+3+4+6+2 = 18
          * Sum Of 1 to N = 1+2+3+4+5+6 = 21
          * Difference Between repeated number and missing number is:
          * X-Y = -3 Or Y-X = 3
          * (5/2)X -X = 3
          * X = 2;
          * Y = 5
          */
         
         Int32 arrLength = arr.Length;
         Int32 ProductOfArrayElements = 1;
         Int32 SumOfArrayElements = 0;
         Int32 X_repeated_num = 0;
         Int32 Y_missing_num = 0;

         for (int idx = 0; idx < arrLength; idx++)
         {
            ProductOfArrayElements *= arr[idx];
            SumOfArrayElements += arr[idx];
         }
           
         Double YinTermsOfXFactor = (Double)ProductOf1ToN/ProductOfArrayElements;

         /*SUM OF ARRAY ELEMENTS - SUM OF 1 to N Numbers  = Sum of Repeated number - Sum of Missing Number */
         Int32 XY_Difference/*X_repeated_num - Y_missing_num*/ = Math.Abs(SumOf1ToN - SumOfArrayElements);
         X_repeated_num = (Int32)Math.Floor(XY_Difference / (YinTermsOfXFactor - 1));
         Y_missing_num = (Int32)Math.Floor(YinTermsOfXFactor * X_repeated_num);
         
         repeatedNum = X_repeated_num;
         missingNum = Y_missing_num;
         return;

      }

another approach can be to sort the nos nd check...(o(nlogn) not efficient .

Is this proper?

public class FindMissingAndDuplicate {
	
	private  static void printMissingAndDuplicate(int[] a){
		Set<Integer> set = new HashSet<Integer>();
		int duplicate = 0;
		long sum = 0;
		boolean isAdded = false;
		for(int i = 0;i<a.length;i++){
			isAdded = set.add(a[i]);
			if(!isAdded){
				duplicate = a[i];
			}
			sum += a[i];
		}
		sum = sum - duplicate;
		long idealSum = (a.length)*((a.length+1)/2);
		long missing = idealSum - sum;
		System.out.println("Duplicate and Missing "+duplicate+" "+missing);
	}
	
	public static void main(String argv[])
	{
	    int[] ar = {1,2,3,4,4}; 
	    printMissingAndDuplicate(ar);
	}

}

another possible solution,
Let the input be 1,4,3,2,4
4 is repeated, 5 is missing.

Sort the array ... after sorting array would be like 1,2,3,4,4

for (int i=0; i<n; i++)
{
if (array[i]!=i+1)
print (" Missing :): %d",i+1)

if (i+1!=n)
{
if (array[i]=array[i+1])
print (" Missing :): %d",i+1)
}
}

According to the question the size of the array is "n". And the array starts from 1 and ends with "n". This means that the size of the array and the last element of the array must be equal?

Am i right?

main()
{
int a[]={3,2,5,1,4,2};
int miss=1, repeat=1;

int t[6] = {0};
for(int i=0; i<6; i++)
{
if(t[a[i]-1] !=0 ) repeat = a[i];
t[a[i]-1] = 1;
}

for(int i=0; i<6; i++)
{
if(t[i] == 0) miss = i+1;
}

printf("miss=%d, repeat=%d\n\r", miss, repeat);

}

package test;

public class MissRepeat {
public static void main(String args[])
{

int[] a = { 5, 4, 3, 1, 1};
int[] b = new int[a.length];

b[0]=a[0];
int x=0,s=0,s1=0;
for (int i = 1; i < a.length; i++)
{
b[i]=a[i];

if(b[i-1]==a[i])
{
x=a[i];
System.out.println("repeated:"+a[i]);
}


}


for (int i = 1; i < a.length+1; i++)
{
s+=i;
s1+=a[i-1];
}


System.out.println("missing:"+(s-s1+x));
}
}

package test;

public class MissRepeat {
public static void main(String args[])
{

int[] a = { 5, 4, 3, 1, 1};
int[] b = new int[a.length];

b[0]=a[0];
int x=0,s=0,s1=0;
for (int i = 1; i < a.length; i++)
{
b[i]=a[i];

if(b[i-1]==a[i])
{
x=a[i];
System.out.println("repeated:"+a[i]);
}


}


for (int i = 1; i < a.length+1; i++)
{
s+=i;
s1+=a[i-1];
}


System.out.println("missing:"+(s-s1+x));
}
}

it can be done using xor.
xor of all given elements and number in range(1,n). will give xor of number not present in array(let it be a), number present twise in array (b).

as we get a xor b.
now we can use the algo of finding 2 non repeated elements of array and numbers in range(0,n). in order on n

We can prevent overflows using this method. You know the number ranges from 1 to n. So make a[a[i]] = 0-a[a[i]]. Scan through the array to find positive numbers. One of them will be repeated and other will be missing. One more scan will help us to find which one is what and reset all of them to positive values

package arrays;

public class FingRepeatingAndMissingElement {

public static void main(String[] args) {
int a[] = { 0, 3, 5, 6, 5, 2, 1 };

for (int i = 0; i < a.length; i++) {
if (a[i] != 0) {
int j = Math.abs(a[i]);
a[j] *= -1;
}
}

int repeating_element = -1;
for (int k = 0; k < a.length; k++) {
if (a[k] > 0) {
repeating_element = a[k];
System.out.println("Repeating element is " + a[k]);
break;
}
}

if (repeating_element != -1) {
int sum = 0;
for (int i = 0; i < a.length; i++) {
sum += Math.abs(a[i]);
}
int missing_element = repeating_element - (sum - 21);
System.out.println("Missing element is " + missing_element);
}
}
}

package page1;

public class FindTheMissingAndRepeatingElement {

/**
* @param args
*/
public static void main(String[] args) {
int a[] = {5,4,4,1,2};
for(int i = 0;i < a.length;i++){
if(a[Math.abs(a[i]) - 1]>0){
a[Math.abs(a[i]) - 1] = - a[Math.abs(a[i]) - 1];
}else
System.out.println(a[i]);
}
for(int i = 0;i< a.length;i++ ){
if(a[i]>0){
System.out.println(i+1);
}
}
}

}

1) exor given array and the complete sequence 1..n. this will give the result (x exor y)
where x and y are single and the double number
2) find the number repeated by iterating and negating the array values, whenever the number is already negated it means the number occured twice
3) exor the number repeated twice with the result in step one. this will return the number which occured only once

In a interview,same question asked to me but only for missing number.
I have answered as:
Sort the array and travers the same and find the missing.

But interviewer asked me that, my solution has 2 traversing
1st sort and than find missing.
He asked me to do in single travers.

Someone can suggest... also considering for repeated number also...

public static void printRepeatedAndMissingNumber(int arr[]){
        int i = 0;
        while(i<arr.length){
            while(arr[i]-1 != i && arr[i] != -1){
                if(arr[i] == arr[arr[i] - 1 ]){
                    System.out.println("repeated  = " + arr[i]);
                    arr[i] = -1;
                    i++;
                }
                else{
                    int temp = arr[arr[i]-1];
                    arr[arr[i]-1]  = arr[i];
                    arr[i] = temp;
                }

            }
            i++;
        }
        for(i = 0; i <arr.length;i++){
            if(arr[i] == -1) System.out.println("missing =" + (i+ 1));
        }

}

i am not really sure if this is O(n) time complexity

Since we know the numbers are consecutive , the max difference of sum of all elements in an array and n*(n+1)/2 is 1

Add the given array to hashset, will get the duplicated element let say 'm' . look for m+1 or m-1 in the hashset. one of them will be missing that is the missing element

A more general solution can be like this :-

#include<iostream>

void swap(int* num1, int* num2)
{
	int nTemp = *num1;
	*num1 = *num2;
	*num2 = nTemp;
}

int main()
{
	int nArray[] = {0, 5, 3, 1, 1, 2};
	int nLength = sizeof(nArray) / sizeof(int);

	int i = 1;
	while(i < nLength)
	{
		if(nArray[i] == i)
		{
			i++;
		}
		else if(nArray[nArray[i]] == nArray[i])
		{
			std::cout << "Repeated no is " << nArray[i] << std::endl;
			i++;
		}
		else
		{
			swap(&nArray[nArray[i]], &nArray[i]);
		}
	}

	i = 1;
	while(i < nLength && nArray[i] == i)
	{
		i++;
	}

	std::cout << "Missing no is " << i << std::endl;

	return 0;
}

#include<iostream>

void swap(int* num1, int* num2)
{
	int nTemp = *num1;
	*num1 = *num2;
	*num2 = nTemp;
}

int main()
{
	int nArray[] = {0, 5, 3, 1, 1, 2};
	int nLength = sizeof(nArray) / sizeof(int);

	int i = 1;
	while(i < nLength)
	{
		if(nArray[i] == i)
		{
			i++;
		}
		else if(nArray[nArray[i]] == nArray[i])
		{
			std::cout << "Repeated no is " << nArray[i] << std::endl;
			i++;
		}
		else
		{
			swap(&nArray[nArray[i]], &nArray[i]);
		}
	}

	i = 1;
	while(i < nLength && nArray[i] == i)
	{
		i++;
	}

	std::cout << "Missing no is " << i << std::endl;

	return 0;
}