Scribd
Upload
3 views

268 find missing element from An unsortd array

The document outlines six methods to find a missing number from an array of the first n natural numbers, detailing their time and space complexities. Methods include using a summation formula, XOR, HashSet, sorting, cyclic sort, and a variation of Gauss' trick with overflow checks. A comparison table summarizes the efficiency and requirements of each method.

Uploaded by

99gopalpandey
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views

268 find missing element from An unsortd array

The document outlines six methods to find a missing number from an array of the first n natural numbers, detailing their time and space complexities. Methods include using a summation formula, XOR, HashSet, sorting, cyclic sort, and a variation of Gauss' trick with overflow checks. A comparison table summarizes the efficiency and requirements of each method.

Uploaded by

99gopalpandey
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

1.

Using Summation Formula (Mathematical Approach)

Time Complexity: O(n)

Space Complexity: O(1)

The sum of the first n natural numbers is given by the formula:

Sum=n×(n+1)2\text{Sum} = \frac{n \times (n+1)}{2}Sum=2n×(n+1)

If we subtract the sum of the given array from this sum, we get the missing number.

Code:

java

CopyEdit

public int missingNumber(int[] nums) {

int n = nums.length;

int expectedSum = n * (n + 1) / 2;

int actualSum = 0;

for (int num : nums) {

actualSum += num;

return expectedSum - actualSum;

2. Using XOR (Bitwise Approach)

Time Complexity: O(n)

Space Complexity: O(1)

Using XOR properties:

• a ⊕ a = 0 (XOR-ing a number with itself cancels it)

• a⊕0=a

If we XOR all numbers in the array with all numbers from 0 to n, the missing number will be left.

Code:
java

CopyEdit

public int missingNumber(int[] nums) {

int xor = 0;

int n = nums.length;

// XOR all numbers from 0 to n

for (int i = 0; i <= n; i++) {

xor ^= i;

// XOR all numbers in the array

for (int num : nums) {

xor ^= num;

return xor;

3. Using HashSet (Extra Space Approach)

Time Complexity: O(n)

Space Complexity: O(n)

We store all numbers in a HashSet and check which number from 0 to n is missing.

Code:

java

CopyEdit

import java.util.HashSet;

public int missingNumber(int[] nums) {


HashSet<Integer> set = new HashSet<>();

for (int num : nums) {

set.add(num);

for (int i = 0; i <= nums.length; i++) {

if (!set.contains(i)) {

return i;

return -1; // This should never be reached

4. Using Sorting (Sorting Approach)

Time Complexity: O(n log n)

Space Complexity: O(1) (if in-place sorting is used)

Sort the array and check which number is missing.

Code:

java

CopyEdit

import java.util.Arrays;

public int missingNumber(int[] nums) {

Arrays.sort(nums);

for (int i = 0; i < nums.length; i++) {

if (nums[i] != i) {
return i;

return nums.length; // If no number is missing in between, return n

5. Using Cyclic Sort (Index Mapping)

Time Complexity: O(n)

Space Complexity: O(1)

Put each number at its correct index (num[i] = i) and check the missing index.

Code:

java

CopyEdit

public int missingNumber(int[] nums) {

int i = 0;

while (i < nums.length) {

int correctIndex = nums[i];

if (correctIndex < nums.length && nums[i] != nums[correctIndex]) {

// Swap nums[i] and nums[correctIndex]

int temp = nums[i];

nums[i] = nums[correctIndex];

nums[correctIndex] = temp;

} else {

i++;

// Find the missing number


for (i = 0; i < nums.length; i++) {

if (nums[i] != i) {

return i;

return nums.length;

6. Using Gauss’ Trick with Overflow Check

To prevent integer overflow in the sum formula method, we sum in chunks.

Code:

java

CopyEdit

public int missingNumber(int[] nums) {

long expectedSum = 0, actualSum = 0;

int n = nums.length;

for (int i = 0; i <= n; i++) {

expectedSum += i;

for (int num : nums) {

actualSum += num;

return (int) (expectedSum - actualSum);

}
Comparison of Methods

Method Time Complexity Space Complexity Notes

Summation Formula O(n) O(1) Might cause integer overflow

XOR Trick O(n) O(1) Efficient, avoids overflow issues

HashSet O(n) O(n) Extra space required

Sorting O(n log n) O(1) Slower than O(n) approaches

Cyclic Sort O(n) O(1) Good if modifying the array is allowed

You might also like