Repeat and Missing Number Array

Given an unsorted array of size n. Array elements are in range from 1 to n. One number from set {1, 2, …n} is missing and one number occurs twice in array. Find these two numbers.

Examples:

  arr[] = {3, 1, 3}
  Output: 2, 3   // 2 is missing and 3 occurs twice 

  arr[] = {4, 3, 6, 2, 1, 1} 

  Output: 1, 5 // 5 is missing and 1 occurs twice

Please Note:

There are certain problems which are asked in the interview to also check how you take care of overflows in your problem. This is one of those problems. Please take extra care to make sure that you are type-casting your ints to long properly and at all places. Try to verify if your solution works if number of elements is as large as 105

Approach is taken from GeeksForGeeks.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

/** * @input A : Read only ( DON'T MODIFY ) Integer array * @input n1 : Integer array's ( A ) length * * @Output Integer array. You need to malloc memory for result array, and fill result's length in length_of_array */ int* repeatedNumber(const int* arr, int n1, int *length_of_array) { *length_of_array = 2; int *result = (int *)malloc(2*sizeof(int)); // SAMPLE CODE int xors = 0; int i; int x = 0, y = 0, setBitNum, flag = 0; // XOR of all elements in the array for(i=0; i<n1; i++) xors = xors ^ arr[i]; // XOR of numbers from 1 to n (with xor) for(i=1; i<=n1; i++) xors = xors ^ i; // Number with the same bit set as the rightmost set bit in xor setBitNum = xors & ~ (xors-1); // Dividing the numbers in two sets and also getting the XORs for(i = 0; i < n1; i++){ if(arr[i] & setBitNum) x = x ^ arr[i]; // arr[i] belongs to Set A else y = y ^ arr[i]; // arr[i] belongs to Set B } for(i = 1; i <= n1; i++){ if(i & setBitNum) x = x ^ i; // arr[i] belongs to Set A else y = y ^ i; // arr[i] belongs to Set B } for(i = 0; i < n1; i++){ if(arr[i] == x){ flag = 1; } } if(flag){ result[0] = x; result[1] = y; }else{ result[0] = y; result[1] = x; } return result; }