1) Contiguous t-sum problem
Given an array A[1..n] and a number t as input, we want to find out if there exists a sub-array whose sum is t. For example, if the following array and t=8 is the input, the answer is YES since it contains the sub-array A[2..4] whose sum is t.
1 4 -1 5 -8 5 -6 3 10 3
2) Distinct-elements problem
Given an array A[1..n], find out if all the elements in the array are distinct. Return YES if all the numbers are distinct NO otherwise.
Suppose we are given an algorithm that solves the t-sum problem in O(n) time. Design an algorithm that solves the distinct-elements problem in O(n) time.
Update (2nd January 2011):
Solution: Posted by Yashoteja (CSE IITB Alumnus, Microsoft Research RA) and Pseudonymous in comment. Thanks