1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Rep Power

    [c] algorithm problem

    Given two sorted arrays of integers of size n,
    i.e. a[n] and b[n], please find all pairs <value_1, value_2>

    so that value from a[n], value_2 from b[n]
    and value_1+ value_2=Constant, e.g. Constant=100.
    and n<100.

    Constraint: O(n) time, O(1) extra space

    i cant think of any way of not using nested loop:(
    pls help me
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Rep Power
    Start with some paper, and some simple examples of short sorted arrays.
    a[] = { 1, 2, 97, 98 };
    b[] = { 3, 4, 95, 98 };
    My suggestion - start at opposite ends of each array.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper

IMN logo majestic logo threadwatch logo seochat tools logo