Question

Given an unsorted array A[] of size N of positive integers. One number 'a' from set {1, 2, …N} is missing and one number 'b' occurs twice in array. The task is to find the repeating and the missing.

Answer 1

#BAL #ANSWERWITHQUALITY

Answer:

Method 1 (Use Sorting)

Approach:

Sort the input array.

Traverse the array and check for missing and repeating.

Time Complexity: O(nLogn)

Thanks to LoneShadow for suggesting this method.

Method 2 (Use count array)

Approach:

Create a temp array temp[] of size n with all initial values as 0.

Traverse the input array arr[], and do following for each arr[i]

if(temp[arr[i]] == 0) temp[arr[i]] = 1;

if(temp[arr[i]] == 1) output “arr[i]” //repeating

Traverse temp[] and output the array element having value as 0 (This is the missing element)

Time Complexity: O(n)

Auxiliary Space: O(n)

Method 3 (Use elements as Index and mark the visited places)

Approach:

Traverse the array. While traversing, use the absolute value of every element as an index and make the value at this index as negative to mark it visited. If something is already marked negative then this is the repeating element. To find missing, traverse the array again and look for a positive value.

Explanation:

I can help you out getting the soln in Py3 and C only,

In Py3 :

def printTwoElements( arr, size):

for i in range(size):

if arr[abs(arr[i])-1] > 0:

arr[abs(arr[i])-1] = -arr[abs(arr[i])-1]

else:

print("The repeating element is", abs(arr[i]))

for i in range(size):

if arr[i]>0:

print("and the missing element is", i + 1)

# Driver program to test above function */

arr = [7, 3, 4, 5, 5, 6, 2]

n = len(arr)

printTwoElements(arr, n)

In C :

#include <stdio.h>

#include <stdlib.h>

void printTwoElements(int arr[], int size)

{

int i;

printf("\n The repeating element is");

for (i = 0; i < size; i++) {

if (arr[abs(arr[i]) - 1] > 0)

arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1];

else

printf(" %d ", abs(arr[i]));

}

printf("\nand the missing element is ");

for (i = 0; i < size; i++) {

if (arr[i] > 0)

printf("%d", i + 1);

}

}

// Driver code

int main()

{

int arr[] = { 7, 3, 4, 5, 5, 6, 2 };

int n = sizeof(arr) / sizeof(arr[0]);

printTwoElements(arr, n);

return 0;

}

Regards,

Arun Bhattacharya