ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Missing Number

prodevelopertutorial March 30, 2020

Problem statement:

You are given an array of numbers from 1 to n, in any order, one number will be missing. You need to find a missing number.

 

Example:

 

Input: [0, 1, 3]

Output: 2

 

We can solve this problem by 2 methods:

 

  1. Finding the sum of all the numbers
  2. Using xor

 

  1. By finding the sum of all the numbers of the array

We know that the sum of all the first n natural numbers can be got by n*(n-1)/2.

 

So first we calculate the sum of “n” numbers.

Then we take the sum of all the numbers present in input array.

Then we subtract both of the result, we get our missing number,

 

Method 2: By using XOR

 

Step 1: We do XOR of all the elements of the array

Step 2: XOR for all the numbers from 1 to n

Step 3: We do XOR of above 2 results, we get our result

 

Solution in C++

 

#include<iostream>
#include<vector>
using namespace std;

int missing_number_using_math(vector<int>& nums) 
{ 
    int len = nums.size();

    int sum = len * (len+1)/2;
    for(int i=0; i<len; i++)
        sum-=nums[i];
    return sum;
}

int missing_number_using_xor(vector<int>& nums) 
{ 
        int missing =0;
        for(int i=0; i<nums.size();++i) 
            missing ^= ((i+1)^nums[i]);
        return missing;
}


int main()
{
	std::vector<int> v = {0, 1, 2, 3, 4, 5, 7};

	cout<<"Missing number using math = "<< missing_number_using_math(v)<<endl;
	cout<<"Missing number using xor = "<< missing_number_using_xor(v)<<endl;

}


 

Output:

Missing number using math = 6
Missing number using xor = 6

 

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2021 ProDeveloperTutorial.com
Get top courses from: Educative.io