1. Home

A Comprehensive Guide on Software Key Tutorials

Elevate your software skills with our comprehensive tutorials covering concepts from basic to advanced techniques. Dive in and become a software pro!

• 220 Lessons
• 37 Hours
132.Â

# Missing Number in Array

Updated on 19/07/20242,281 Views

## Introduction

Finding a missing number in array is a regular trouble in the realm of programming and algorithmic critical thinking. This issue arises when a series of successive numbers have one element missing and our objective is to quickly locate the part that is missing. Developers must be able to solve these kinds of difficulties since it exhibits their analytical thinking and problem-solving abilities. Using well-known programming languages including Java, C, C , Python, and JavaScript, we will examine numerous methods for resolving the missing number in array Javascript problem in this article. You will learn useful information about several tactics that may be used to quickly locate and publish the missing number in an array by comprehending and putting these techniques into practice. So let's get started and learn this problem-solving technique!

## Overview

The missing number in the array problem can be approached from multiple angles. In this blog, we will discuss six different methods to find the missing number, each with its own unique approach and implementation. These methods provide efficient solutions for identifying the missing number in array C++ by utilizing techniques such as hashing, summation of first N natural numbers, binary operations, cyclic sort, using elements as an index, and bit manipulation. By understanding and implementing these approaches in various programming languages, programmers can enhance their problem-solving skills and algorithmic thinking abilities, leading to more effective solutions for similar problems.

## Find the Missing Number

Now, let's dive into each approach and explore their implementation in the mentioned programming languages.

• ### Approach 1: Using Hashing

The initial approach entails utilizing a hash table to maintain track of the array's elements. We can find the missing number by looking for the missing key while iterating through the array and adding each member to the hash table.

We will demonstrate the implementation of this approach in Java:

`import java.util.*;public class MissingNumber {Â  Â  public static int findMissingNumber(int[] nums) {Â  Â  Â  Â  Â Set<Integer> set = new HashSet<>();Â  Â  Â  Â  for (int num : nums) {Â  Â  Â  Â  Â  Â  Â set.add(num);Â  Â  Â  Â  }Â  Â  Â  Â  int n = nums.length 1;Â  Â  Â  Â  for (int i = 1; i <= n; i ) {Â  Â  Â  Â  Â  Â  if (!set.contains(i)) {Â  Â  Â  Â  Â  Â  Â  Â  return i;Â  Â  Â  Â  Â  Â  }Â  Â  Â  Â  }Â  Â  Â  Â  return -1; // No missing number foundÂ  Â  }Â  Â  public static void main(String[] args) {Â  Â  Â  Â  int[] nums = {1, 2, 4, 5}; // Missing number: 3Â  Â  Â  Â  int missingNumber = findMissingNumber(nums);Â  Â  Â  Â  Â System.out.println("Missing number: " missingNumber);Â  Â  }}`
• ### Approach 2: Using Summation of First N Natural Numbers

Using this approach, we add the first N natural numbers according to the summation formula. The missing number in array C can be found by computing the expected sum and deducting it from the array's element sum.

Let's analyze the execution of this approach in Python:

`def find_missing_number(nums):Â  Â  n = len(nums) 1Â  Â  expected_sum = (n * (n 1)) // 2Â  Â  actual_sum = sum(nums)Â  Â  return expected_sum - actual_sumnums = [1, 2, 4, 5] # Missing number: 3missing_number = find_missing_number(nums)print("Missing number:", missing_number)`
• ### Approach 3: Using Binary Operations

By performing bitwise XOR operations on all the elements in the array and the numbers from 1 to N, we can find the missing number. XORing the same number twice results in zero, leaving only the missing number in the final XOR value.

Let's implement this approach in JavaScript:

`function findMissingNumber(nums) {Â  Â  let n = nums.length 1;Â  Â  let xorValue = 0;Â  Â  for (let i = 1; iÂ <= n; i ) {Â  Â  Â  Â  xorValue ^= i;Â  Â  }Â  Â  for (let num of nums) {Â  Â  Â  Â  xorValue ^= num;Â  Â  }Â  Â  return xorValue;}let nums = [1, 2, 4, 5]; // Missing number: 3let missingNumber = findMissingNumber(nums);console.log("Missing number:", missingNumber);`
• ### Approach 4: Using Cyclic Sort

The cyclic sort technique can also be applied to find the missing number in array. By sorting the array in its natural order and then iterating through it, we can identify the first instance where the index does not match the element value, indicating the missing number.

Let's explore this approach in C:

`#include <iostream>#include <vector>using namespace std;int findMissingNumber(vector<int>& nums) {Â  Â  int i = 0;Â  Â  while (i < nums.size()) {Â  Â  Â  Â  if (nums[i] < nums.size() && nums[i] != nums[nums[i]]) {Â  Â  Â  Â  Â  Â  Â swap(nums[i], nums[nums[i]]);Â  Â  Â  Â  } else {Â  Â  Â  Â  Â  Â  i ;Â  Â  Â  Â  }Â  Â  }Â  Â  for (int i = 0; i < nums.size(); i ) {Â  Â  Â  Â  if (nums[i] != i) {Â  Â  Â  Â  Â  Â  return i;Â  Â  Â  Â  }Â  Â  }Â  Â  return nums.size();}int main() {Â  Â  vector<int> nums = {1, 2, 4, 5}; // Missing number: 3Â  Â  int missingNumber = findMissingNumber(nums);Â  Â  cout << "Missing number: " << missingNumber << endl;Â  Â  return 0;}`
• ### Approach 5: Using Elements as Index and Marking Visited Places as Negative

The fact that the array's integers vary from 1 to N is used to this approach's benefit. We may quickly locate the index with a positive value, indicating the missing number, by iterating over the array and marking the visited locations as negative.

Let's see this approach in action with C:

`#include <stdio.h>#include <stdlib.h>int findMissingNumber(int nums[], int size) {Â  Â  for (int i = 0; i < size; i ) {Â  Â  Â  Â  int index = abs(nums[i]) - 1;Â  Â  Â  Â  if (index < size) {Â  Â  Â  Â  Â  Â  Â nums[index]= -abs(nums[index]);Â  Â  Â  Â  }Â  Â  }Â  Â  for (int i = 0; i < size; i ) {Â  Â  Â  Â  if (nums[i] > 0) {Â  Â  Â  Â  Â  Â  return i 1;Â  Â  Â  Â  }Â  Â  }Â  Â  return size 1;}int main() {Â  Â  int nums[] = {1, 2, 4, 5}; // Missing number: 3Â  Â  int size = sizeof(nums) / sizeof(nums[0]);Â  Â  int missingNumber = findMissingNumber(nums, size);Â  Â  Â printf("Missing number: %d\n", missingNumber);Â  Â  return 0;}`
• ### Approach 6: Using Bit Manipulation (XOR)

Similar to the third approach, bit manipulation using XOR can be utilized to find the missing number. An XOR operation will be utilized to track down the missing number by consolidating the exhibit of all array's members with the numbers from 1 to N.

Here's an example of implementing this approach in Java:

`public class MissingNumber {Â  Â  public static int findMissingNumber(int[] nums) {Â  Â  Â  Â  int xorValue = 0;Â  Â  Â  Â  for (int i = 0; i < nums.length; i ) {Â  Â  Â  Â  Â  Â  xorValue ^= nums[i] ^ (i 1);Â  Â  Â  Â  }Â  Â  Â  Â  return xorValue ^ (nums.length 1);Â  Â  }Â  Â  public static void main(String[] args) {Â  Â  Â  Â  int[] numsÂ = {1, 2, 4, 5}; // Missing number: 3Â  Â  Â  Â  int missingNumber = findMissingNumber(nums);Â  Â  Â  Â  Â System.out.println("Missing number: " missingNumber);Â  Â  }}`

## How to Print a Missing Number in Array?

To print the missing number in addition to finding it, you can simply modify the code snippets provided for each approach. Instead of returning the missing number, you can print it directly. For example, in Java:

`for (int i = 1; i <= n; i ) {Â  Â  if (!set.contains(i)) {Â  Â  Â  Â  System.out.println("Missing number: " i);Â  Â  Â  Â  break;Â  Â  }}`

Similarly, for the other approaches, you can incorporate a print statement within the code logic to display the missing number. By doing so, you can visually observe the result directly without examining the returned value separately. Printing the missing number enhances the user experience and provides a clear output for analysis and verification purposes.

## Conclusion

In conclusion, the missing number in array python problem offers various approaches that can be implemented in different programming languages. Through the exploration of hashing, summation of first N natural numbers, binary operations, cyclic sort, using elements as index, and bit manipulation, programmers gain valuable problem-solving skills and enhance their algorithmic thinking abilities. These techniques provide efficient solutions to identify and print the missing number in array Java. By understanding and practicing these approaches, developers can strengthen their programming expertise and tackle similar challenges with confidence, making them more versatile and adept problem solvers in the world of software development. So, embrace these approaches, hone your skills, and embark on your journey towards becoming an exceptional programmer. Happy coding!

## FAQs

1. Is the missing number always guaranteed to be a single element?

Yes, in the given problem statement, we assume that there is only one missing number in the array. These approaches are specifically designed to find a single missing element efficiently. If there are multiple missing numbers, the approaches discussed may not yield accurate results without modifications.

2. When the array is empty, what happens?

These methods are unable to identify the missing number if the array is empty since there are no elements to examine. To prevent unexpected behavior or program faults, it is crucial to treat such edge situations independently.

3. Can these approaches be used to find multiple missing numbers in an array?

No, the approaches discussed in this blog are specifically designed to find a single missing number in an array of consecutive elements. To find multiple missing numbers, different techniques and modifications to the approaches would be necessary.

4. Do these approaches work for non-consecutive numbers in an array?

No, these approaches assume that the array consists of consecutive numbers with one missing element. These methods might not produce reliable results if the array has irregular or non-consecutive numbers. Alternative techniques tailored to the provided array pattern would need to be used in such circumstances.

5. Are these approaches applicable to arrays with duplicate elements?

Yes, these approaches can handle arrays with duplicate elements. The identification of the missing number is unaffected by the duplicate items since it is expected to be the sole unique element in the array. Instead of looking for duplicates, the techniques concentrate on the lack of a certain element.

Director of Engineering

Director of Engineering @ upGrad. Motivated to leverage technology to solve problems. Seasoned leader for startups and fast moving orgs. Working â€¦Read More

###### Get Free Career Counselling
+91
*
By clicking, I accept theT&Cand
Join 10M+ Learners & Transform Your Career
Learn on a personalised AI-powered platform that offers best-in-class content, live sessions & mentorship from leading industry experts.

Talk to our experts. Weâ€™re available 24/7.

Indian Nationals

1800 210 2020

Foreign Nationals

+918045604032

## Disclaimer

upGrad does not grant credit; credits are granted, accepted or transferred at the sole discretion of the relevant educational institution offering the diploma or degree. We advise you to enquire further regarding the suitability of this program for your academic, professional requirements and job prospects before enr...