Popular Posts

  • Amazon "Bar Raiser" Interview Question
    Given the sequence  S1  = {a,b,c,d,…,x,y,z,aa,ab,ac…. } and given that this sequence corresponds (term for term) to the sequence  S2  = {0,1...
  • Maximum size square sub-matrix with all 1s
    Given a binary matrix, find out the maximum size square sub-matrix with all 1s. Algorithm: Let the given binary matrix be M[R][C]. The idea ...
  • The Sports Stadium
    The bustling town of Siruseri has just one sports stadium. There are a number of schools, colleges, sports associations, etc. that use this ...
  • Shell sort
    Refer :  http://education.cdacmumbai.in/education/pgdst/dsalfac/notes/ShellSort.pdf Shellsort works by comparing elements that are distant r...
  • Gmail Multiple User Names...
    Many of you might not be knowing that if you have 1 gmail id … you have infinte gmail ids… Seems to be a joke.. It’s not actually… for e.g ...
  • Find Kth largest and smallest number in BST
    How to find  kth  smallest element in BST . you cannot use static/global variable and you cannot pass value of k to any function ? Solution ...
  • Maximum Area Rectangle In Histogram
    Find the maximum rectangle (in terms of area) under a histogram in linear time. I mean the area of largest rectangle that fits entirely in t...
  • Maximum Difference In An Array
    There is an integer array consisting positive and negative integers. Find maximum positive difference S defined as: O(N) solution S  = a[i] ...
  • 3 sum and 2 sum problem
    Q: Given an integer x and an unsorted array of integers, describe an algorithm to determine whether two of the numbers add up to x. If we ha...
  • Remove duplicate nodes in Binary Search Tree
    http://effprog.blogspot.com/2011/02/duplicate-removal-in-binary-search-tree.html http://shashank7s.blogspot.com/2011/03/write-program-to-rem...

Tuesday, March 22, 2011

Find missing number in an array

An array A[1...n] contains all the integers from 0 to n except for one  number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is “fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer.


http://groups.google.com/group/algogeeks/browse_thread/thread/73f0092cb54b1904





Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)