Skip to main content

Array Problems - Contiguous Sum and Distinct Elements

Source: Posted by Algo Muse on contact page. Also posted on Algo Muse (December 2011) http://www.algomuse.appspot.com

Problem:

Two definitions:

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.

Real Problem:

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

Comments

  1. 1. A nlogn time n space approach:
    Let Ai be the given numbers.
    Bi = Sum (j=1 to i) Ai

    Subarray sum,
    Sij = Sum (k=i to j) Ai = Bj-B(i-1)

    Now we can build a Binary Search Tree of Bis.
    Starting from i=1 and moving on, remove Bi from the tree and search for Bi+t among remaining elements in the tree. If you find such an element then answer is YES o.w. NO

    2. Can use BST again

    3. Let Ai be the given numbers
    Bi = A(i+1)-Ai
    Now Aj-Ai = Sum (k=i to (j-1)) Bi
    Hence distinct-elements problem reduced to t-sum in O(n), with t=0

    ReplyDelete
  2. Reduction of Distinct-Elements (DE) to Contiguous-t-Sum (CtS):

    Given an array A:{a_1, a_2,..., a_n}, form the array B:{b_1, b_2,..., b_n-1}, where b_i = a_i+1 - a_i. Clearly, this takes O(n) time.

    There exist i, j such that a_i = a_j, iff there is a contiguous sub-array of B that sums to zero. Hence to solve DE for A, simply run the CTS algorithm for B, testing for sum = 0.

    ReplyDelete
  3. Correct solution by both Yashoteja and Pseudonymous. Thanks

    ReplyDelete
  4. i didnt get the above solution of questio 1.... can u make it clear or give me the code plz....

    ReplyDelete
  5. Sum the elements from left to right. Lets call this sum_lr.

    Sum the elements from right to left. Call this sum_rl.

    now t = sum_lr(i) - sum_lr(j) for some i,j given i>j
    also for the same i, j
    t = sum_rl(j) - sum_rl(i)

    these two equations imply
    sum_rl(i)+sum_lr(i) = sum_rl(j)+sum_lr(j) for those i,j

    thus we form another array, lets call it sum such that
    sum(k) = sum_rl(k) + sum_lr(k)

    we want to find out the duplicates in this array sum and those will be candidates for i,j. This is basically the second problem.

    To find out if there are duplicates, the simplest way would be to sort the array. Once sorted we check out the duplicates and see if the sum is really t for those indices.

    ReplyDelete

Post a Comment

Popular posts from this blog

Asking a girl out

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this article though :P

Most of my friends already read an article that I wrote more than an year back - "Speak Up"


Here, inspired by the movie, The Beautiful Mind, I give a mathematical analysis of asking a girl out. Nice time it is. Feb 10. No plans for Feb 14 and I am sure this article makes me look even more geekier and all the more reason for me to believe that I will be alone, yet again. But what the hell, lets do it!

Note: This is not an independent analysis. There are many "mathematics sites" which does "similar" analysis.

@Consultants, correct me if I am wrong in my estimates. :P

Why is there a need to be selective?

From the age of 15, I guess there are approximately 3,600 girls I have liked (On average days, I don't see new girls. But going outside, I like about 30 girls. Saying that I go out once every week right …

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process.

1) Calculate P{X>Y}
2) What's the expected value of X
3) What's the expected value of Y

This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment.

Solution:
1)
(Solved by me finally after 13 months :))

Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently.

So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0"

f(State) = P(X>Y | "State" configuration initially)

f(0,0) = 1/4[f(…

Fraction Brainteaser

Source:
Sent to me by Gaurav Sinha

Problem:
Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions. In total, Siddhant scores 25 out of 34. 

Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34.

Note that
a) Vaibhav scores more than Siddhant
b) Siddhant score better than Vaibhav in both individual topics - 5/6 > 20/25 and 20/28 > 6/9

How is it possible?