# 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 find the exact element usnig xpath

» how to find element by attribute in webdriver

» Finding element by content with scLocator?

» How to implement logic: if element exist in the list (array), Se, Selenise

» Element not found error and quits in explorer / runs in firefox

» how to find element by attribute in webdriver

» Finding element by content with scLocator?

» How to implement logic: if element exist in the list (array), Se, Selenise

» Element not found error and quits in explorer / runs in firefox

Page

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

**cannot**reply to topics in this forum