{"post":"

Problem

You are given an array of n integers from 1 to n. Each integer appears exactly once except A which appears twice and B which is missing. Print A and B.

Brute Force Approach

Using sorting

Sort the given array and traverse the array. If the element is not equal to i+1, then the i+1 is missing and arr[i] is duplicate.

TC – O(NlogN)

SC – O(1)

Better Approach

Using HashMap

Put all the array elements in the hashmap with their occurrence count. Iterate from 1 to n and check their occurrence count in the map, if count is greater than 1 then the number is duplicate else if the key doesn’t exist means the element is missing.

TC – O(N)

SC – O(N)

Optimal Approach

Using swap sort

We’ll check if the element is not at its right place swap it with its correct position.

#include<bits/stdc++.h>\nusing namespace std;\n\nvoid printMissingAndDuplicateNum(int arr[],int arrSize){\n  int i = 0;\n  \n  while(i < arrSize){\n    if(arr[i] != arr[arr[i]-1]) \n      swap(arr[i], arr[arr[i]-1]);\n    } else {\n      i++;\n    }\n  }\n\t\n  for(int i = 0; i<arrSize; i++){\n  \tcout<<arr[i]<<\" \";\n  }\n  cout<<endl;\n  for(int i = 0; i<arrSize; i++){\n  \tif(arr[i] != i+1){\n    \tcout<<\"Missing Number : \"<< i + 1<<endl;\n      \tcout<<\"Duplicate Number : \"<< arr[i]<<endl;\n    }\n  }\n}\n\nint main(){\n  int arr[] = {1,2,2,4};\n  int arrSize = sizeof(arr)/sizeof(arr[0]);\n  printMissingAndDuplicateNum(arr, arrSize);\n  return 0;\n}\n

TC – O(N) // in worst case first element is swapped with all other

SC – O(1)

Using Bit Manipulation(If the array is read-only)

First, we’ll find the xor of 1 to n and arr[0] to arr[n-1]. Then find the right significant(RSB) bitmask of xor, and now divide the elements into two parts one with RSB set and the other with RSB not set.

#include<bits/stdc++.h>\nusing namespace std;\n\nvoid printMissingAndDuplicateNum(int arr[],int arrSize){\n   int xorr = 0;\n   for(int i = 0 ; i < arrSize; i++){\n       xorr ^= arr[i];\n       xorr ^= (i + 1);\n   }\n  \n   int rightSignificantBitMask = xorr & (-xorr);\n   \n   int x = 0;\n   int y  = 0;\n   for(int i = 0 ; i < arrSize; i++){\n       if((rightSignificantBitMask & arr[i]) == 0){\n           x ^= arr[i];\n       }else{\n           y ^= arr[i];\n       }\n   }\n   \n   for(int i = 1 ; i <= arrSize; i++){\n       if((rightSignificantBitMask & i) == 0){\n           x ^= i;\n       }else{\n           y ^= i;\n       }\n   }\n   \n   for(int i = 0 ; i < arrSize; i++){\n       if(arr[i] == x){\n         \tcout<<\"Missing Num : \"<<y<<endl;\n         \tcout<<\"Duplicate Num : \"<<x<<endl;\n           \tbreak;\n       }\n       \n       if(arr[i] == y){\n         \tcout<<\"Missing Num : \"<<x<<endl;\n         \tcout<<\"Duplicate Num : \"<<y<<endl;\n          \tbreak;\n       }\n   }\n}\n\nint main(){\n  int arr[] = {1,2,2,4};\n  int arrSize = sizeof(arr)/sizeof(arr[0]);\n  printMissingAndDuplicateNum(arr, arrSize);\n  return 0;\n}\n

\n","title":"Repeat and missing number in array","authorDetails":{"name":"studymite","slug":"admin"},"description":"Here we'll find repeat and missing numbers in array using different methods. We will use xor bit manipulation.","slug":"repeat-and-missing-number-in-array/","articleId":"636a83417bb1ce5072622b0a","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}