Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 2 down vote favorite
7

Given an array of N positive integers. It can have n*(n+1)/2 sub-arrays including single element sub-arrays. Each sub-array has a sum S. Find S's for all sub-arrays is obviously O(n^2) as number of sub-arrays are O(n^2). Many sums S's may be repeated also. Is there any way to find count of all distinct sum (not the exact values of sums but only count) in O(n logn).

I tried an approach but stuck on the way. I iterated the array from index 1 to n.
Say a[i] is the given array. For each index i, a[i] will add to all the sums in which a[i-1] is involved and will include itself also as individual element. But duplicate will emerge if among sums in which a[i-1] is involved, the difference of two sums is a[i]. I mean that, say sums Sp and Sq end up at a[i-1] and difference of both is a[i]. Then Sp + a[i] equals Sq, giving Sq as a duplicate.

Say C[i] is count of the distinct sums in which end up at a[i].
So C[i] = C[i-1] + 1 - numbers of pairs of sums in which a[i-1] is involved whose difference is a[i].

But problem is to find the part of number of pairs in O(log n). Please give me some hint about this or if I am on wrong way and completely different approach is required problem point that out.

share|improve this question
Well, it's an interesting problem. Everything I'm coming up with potentially requires considering all pairs of input elements, which is O(n^2). My gut says it's impossible. – user2357112 Jul 6 at 21:50
I have been assured by one who gave me the problem that O(n logn) exists. I spent whole day thinking. – user2011120 Jul 6 at 21:55
If you're still stuck tomorrow, ask him for a timeable demo, so you know he's not messing with you. – user2357112 Jul 6 at 21:58
4  
@all This is an active programming contest question. Please do not answer this. codechef.com/JULY13/problems/FARASA – banarun Jul 7 at 4:48
20  
Flaggers: We are aware that this is an ongoing Code Chef challenge. While this question may violate the spirit of the challenge, it does not violate the rules of Stack Overflow and does not warrant deletion. Please do not keep flagging it for deletion. – animuson♦ Jul 7 at 16:49
show 10 more comments

2 Answers

up vote 10 down vote accepted

When S is not too large, we can count the distinct sums with one (fast) polynomial multiplication. When S is larger, N is hopefully small enough to use a quadratic algorithm.

Let x_1, x_2, ..., x_n be the array elements. Let y_0 = 0 and y_i = x_1 + x_2 + ... + x_i. Let P(z) = z^{y_0} + z^{y_1} + ... + z^{y_n}. Compute the product of polynomials P(z) * P(z^{-1}); the coefficient of z^k with k > 0 is nonzero if and only if k is a sub-array sum, so we just have to read off the number of nonzero coefficients of positive powers. The powers of z, moreover, range from -S to S, so the multiplication takes time on the order of S log S.

share|improve this answer
Nice, I think this is the correct approach. – Niklas B. Jul 7 at 11:04
2  
This answer has been up long enough that it would be unfair to remove it now. Please don't vandalize it. – David Eisenstat Jul 7 at 16:46
@David Few people are trying hard to get problem removed but moderators are ignoring them. Its one of the decisive problem of the contest. I am not accepting it to not give anyone hint of it. Can you please delete the solution now and re-post after contest is over. I will mark it accepted thereafter. – user2011120 Jul 7 at 17:36
6  
@user2011120: We're not ignoring them - you can see the comment above. We're just refusing them. Neither David nor others are obligated to remove their answers, nor are we to remove your question. You will have to take responsibility for your own actions; do not try to eschew this responsibility onto others. That is just selfish and unfair. – BoltClock♦ Jul 8 at 15:15
After knowing that its live competition question. My responsibility becomes to get it removed to keep spirit of competition. I tried everything to remove it. Since deletion is not under my control. So what most I can do is to request the replier. – user2011120 Jul 9 at 9:53
show 1 more comment
up vote 0 down vote

You can look at the sub-arrays as a kind of tree. In the sense that subarray [0,3] can be divided to [0,1] and [2,3].

So build up a tree, where nodes are defined by length of the subarray and it's staring offset in the original array, and whenever you compute a subarray, store the result in this tree.

When computing a sub-array, you can check this tree for existing pre-computed values.

Also, when dividing, parts of the array can be computed on different CPU cores, if that matters.

This solution assumes that you don't need all values at once, rather ad-hoc. For the former, there could be some smarter solution.

Also, I assume that we're talking about counts of elements in 10000's and more. Otherwise, such work is a nice excercise but has not much of a practical value.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.