Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

#1
February 15th, 2013, 10:10 AM
Registered User

Join Date: Feb 2013
Posts: 1
Time spent in forums: 5 m 49 sec
Reputation Power: 0
[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
February 15th, 2013, 10:57 AM
 salem
Contributed User

Join Date: Jun 2005
Posts: 3,905
Time spent in forums: 2 Months 3 Weeks 4 Days 1 h 2 m 13 sec
Reputation Power: 1774
Start with some paper, and some simple examples of short sorted arrays.
Code:
```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

 Viewing: Dev Shed Forums > Programming Languages > C Programming > [c] algorithm problem