Find the missing element in the array

Go down

Find the missing element in the array

Post  Admin on Sun Aug 03, 2008 6:03 am

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

View user profile http://computerclub09mnnit.forumotion.net

Back to top Go down

Re: Find the missing element in the array

Post  mnnit.rahul on Mon Aug 11, 2008 3:14 am

# 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");
}

mnnit.rahul

Posts : 16
Join date : 2008-08-10

View user profile

Back to top Go down

Using Part of Count Sort

Post  shivang on Mon Aug 11, 2008 7:19 am

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
avatar
shivang

Posts : 22
Join date : 2008-08-11
Age : 29
Location : Tondon 174

View user profile

Back to top Go down

faster version

Post  ankurgutpa on Mon Aug 11, 2008 11:31 am

missing_element=0
for i=1 to n{
missing_element^=(i^a[i]);
}
print missing element cheers
avatar
ankurgutpa

Posts : 44
Join date : 2008-08-10
Age : 30
Location : Tandon 72

View user profile

Back to top Go down

@Ankur

Post  shivang on Mon Aug 11, 2008 9:48 pm

How come this is a faster version???
avatar
shivang

Posts : 22
Join date : 2008-08-11
Age : 29
Location : Tondon 174

View user profile

Back to top Go down

Re: Find the missing element in the array

Post  ankurgutpa on Tue Aug 12, 2008 1:51 am

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. cheers
avatar
ankurgutpa

Posts : 44
Join date : 2008-08-10
Age : 30
Location : Tandon 72

View user profile

Back to top Go down

mnnit.rahul

Post  bhagalpur on Tue Aug 12, 2008 1:55 am

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

bhagalpur

Posts : 3
Join date : 2008-08-03

View user profile

Back to top Go down

shivang

Post  bhagalpur on Tue Aug 12, 2008 1:56 am

Re think of your solution and try to give algo of the solution

bhagalpur

Posts : 3
Join date : 2008-08-03

View user profile

Back to top Go down

Re: Find the missing element in the array

Post  Dee2306 on Tue Aug 12, 2008 10:03 am

ankurgutpa wrote:missing_element=0
for i=1 to n{
missing_element^=(i^a[i]);
}
print missing element cheers

Smile Too Good.. Basketball
avatar
Dee2306

Posts : 7
Join date : 2008-08-12
Age : 30

View user profile

Back to top Go down

Re: Find the missing element in the array

Post  shivang on Tue Aug 12, 2008 1:02 pm

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
avatar
shivang

Posts : 22
Join date : 2008-08-11
Age : 29
Location : Tondon 174

View user profile

Back to top Go down

Re: Find the missing element in the array

Post  ankurgutpa on Tue Aug 12, 2008 3:33 pm

question is same but try to do it by following constraint
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) .
avatar
ankurgutpa

Posts : 44
Join date : 2008-08-10
Age : 30
Location : Tandon 72

View user profile

Back to top Go down

Re: Find the missing element in the array

Post  Sponsored content


Sponsored content


Back to top Go down

Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum