2nd part can be done just take the xor of all the numbers same number xor returns 0 so only seven will remain. 1st part can be done in O(n) because estimate sum -> n*(n+1)/2. now sub from estimated sum each array element. the last value remained is the missing number. correct me if i am wrong.
On Thu, Jun 9, 2011 at 9:59 AM, Ershad K <[email protected]> wrote: > On Thursday 09 June 2011 03:15 PM, Dumanshu wrote: > >> Q1. I have a file in which there are supposed to be 4 billion >> numbers, >> starting from 1 to 4,000,000,000 but unfortunately one number is >> missing, >> i.e there are only 3,999,999,999 numbers, I need to find the missing >> number. >> > > Is the array sorted? > > -- > Sincerely, > Ershad K > http://ershadk.wordpress.com > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Varun Pahwa B.Tech (IT) 7th Sem. Indian Institute of Information Technology Allahabad. Ph : 09793899112 ,08011820777 Official Email :: [email protected] Another Email :: [email protected] People who fail to plan are those who plan to fail. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
