# Find the missing element in the array

## Find the missing element in the array

Suppose we have an array A containing elements from 1 to n. An element is made zero and the resulting array is called B. Find the element that was made zero. Consider all the test cases and boundary conditions. Try to post multiple solutions. (This question was asked in Adobe written exam)

**Admin**- Admin
- Posts : 39

Join date : 2008-08-03

## Re: Find the missing element in the array

# include<iostream>

using namespace std;

main()

{int n,i,s1=0,s2=0;

cin>>n;

int a[n];

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

{cin>>a[i];

s2+=a[i];

}

s1=(n*(n+1))/2;

cout<<s1-s2;

system("pause");

}

using namespace std;

main()

{int n,i,s1=0,s2=0;

cin>>n;

int a[n];

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

{cin>>a[i];

s2+=a[i];

}

s1=(n*(n+1))/2;

cout<<s1-s2;

system("pause");

}

**mnnit.rahul**- Posts : 16

Join date : 2008-08-10

## Using Part of Count Sort

for i <--- 1 to n

{do C[i] <- 0

}

for j <--- 1 to n

{do C[A[j]] <--- C[A[j]] + 1

}

for i <--- 1 to n

{if C[i] == 0

then Break

}

outpu i

{do C[i] <- 0

}

for j <--- 1 to n

{do C[A[j]] <--- C[A[j]] + 1

}

for i <--- 1 to n

{if C[i] == 0

then Break

}

outpu i

**shivang**- Posts : 22

Join date : 2008-08-11

Age : 30

Location : Tondon 174

## faster version

missing_element=0

for i=1 to n{

missing_element^=(i^a[i]);

}

print missing element

for i=1 to n{

missing_element^=(i^a[i]);

}

print missing element

**ankurgutpa**- Posts : 44

Join date : 2008-08-10

Age : 31

Location : Tandon 72

## Re: Find the missing element in the array

faster not in terms of asymptotic notation but it will take less time as

bitwise operations are faster than addition/subtraction are faster than multiply/divide are faster than comparison.

bitwise operations are faster than addition/subtraction are faster than multiply/divide are faster than comparison.

**ankurgutpa**- Posts : 44

Join date : 2008-08-10

Age : 31

Location : Tandon 72

## mnnit.rahul

What if n(n+1)/2 exceeds the limit of integer ???

**bhagalpur**- Posts : 3

Join date : 2008-08-03

## Re: Find the missing element in the array

ankurgutpa wrote:missing_element=0

for i=1 to n{

missing_element^=(i^a[i]);

}

print missing element

**Too Good..**

**Dee2306**- Posts : 7

Join date : 2008-08-12

Age : 30

## Re: Find the missing element in the array

ya der was one problem.....the 0 wud hav created the problem.....

thanx.....

The algo tat'll work

for i <--- 0 to n

{do C[i] <- 0

}

for j <--- 1 to n

{do C[A[j]] <--- C[A[j]] + 1

}

for i <--- 0 to n

{if C[i] == 0

then Break

}

output i

thanx.....

The algo tat'll work

for i <--- 0 to n

{do C[i] <- 0

}

for j <--- 1 to n

{do C[A[j]] <--- C[A[j]] + 1

}

for i <--- 0 to n

{if C[i] == 0

then Break

}

output i

**shivang**- Posts : 22

Join date : 2008-08-11

Age : 30

Location : Tondon 174

## Re: Find the missing element in the array

question is same but try to do it by following constraint

O(nlogn) solution exist for this problem but try to do it in O(n) ( as stated in CLRS 4-2) .

**you can only fetch jth bit of an element of array(assume in constant time) and nothing else**O(nlogn) solution exist for this problem but try to do it in O(n) ( as stated in CLRS 4-2) .

**ankurgutpa**- Posts : 44

Join date : 2008-08-10

Age : 31

Location : Tandon 72

Similar topics

» How to create/recognize object element not using recording?

» Selenium 2 Webdriver cant find element by xpath after upgrading from firefox 3.6 to 5

» Cannot locate the class Select in web driver

» TestSuites and TestResults with Selenium WebDrive API

» Fishing Resort Tournament 3/4/12-3/18/12 Tidur River

» Selenium 2 Webdriver cant find element by xpath after upgrading from firefox 3.6 to 5

» Cannot locate the class Select in web driver

» TestSuites and TestResults with Selenium WebDrive API

» Fishing Resort Tournament 3/4/12-3/18/12 Tidur River

Page

**1**of**1****Permissions in this forum:**

**cannot**reply to topics in this forum