@anoop
when you find some i and j(i < j) meet the condition i.e. asq[i] + asq[j] ==
asq[k], you can merge the same value without rollback.
in this sense, you are right.
On Thu, Dec 2, 2010 at 2:26 PM, anoop chaurasiya wrote:
> @fenghuang try this array:
> a[]={3,3,3,3,3,3,4,4,4,4,4,4,5}
> so as
@fenghuang try this array:
a[]={3,3,3,3,3,3,4,4,4,4,4,4,5}
so asq[]={9,9,9,9,9,9,16,16,16,16,16,16,25}
here as u can see the total number of requisite triple pairs are 6*6=36,
in general for above array total number of pairs is (n/2)*(n/2) i.e. n^2/4
where n is the size of the array.
by using O(n)
@anoop
in fact, it always work even if there are repeated elements, because they
don't change the decision.
in detail, assume ii, ,jj, kk is one of the answers, then a[ii]+a[jj]=a[kk].
since the array is sorted, so a[ii-1]+a[jj] <= a[kk] and a[ii] + a[jj+1] >=
a[kk].
so when you try the pair of 'i
sorry for the interruption,we can make it work even if the elements are
repeated, by removing the duplicacy in linear time(as the array is already
sorted) and taking a count of no. of duplicates in the seperate array.
On Wed, Dec 1, 2010 at 9:37 PM, Senthilnathan Maadasamy <
senthilnathan.maadas..
A small correction to the algorithm above. In Step 3, instead of finding *
any* pair (a,b) such that a+b = x we need to find *all* such pairs. However
the complexity remains the same.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post
@DEV,your idea is nice.but i think it wont work in case the array is
having repeated elementsam i right
On Wed, Dec 1, 2010 at 1:51 PM, nishaanth wrote:
> I have a O(n^2) solution..
>
> Hash all the squares.0(n)
>
> Now for every pair find the sum, see if its there in the hash t
I have a O(n^2) solution..
Hash all the squares.0(n)
Now for every pair find the sum, see if its there in the hash table.O(n^2)
Total complexity : O(n^2)
On Wed, Dec 1, 2010 at 11:00 PM, fenghuang wrote:
> yeah, you're right. thank you and is it the optimal solution about this
> questio
Someone please explain why do we need dynamic programming approach to solve
this? Cant we find the solution as mentioned by 'algose chase' above??
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@
yeah, you're right. thank you and is it the optimal solution about this
question?
On Thu, Dec 2, 2010 at 1:08 AM, Dave wrote:
> @Fenghuang: No. You don't have to search for b for every a, or more
> precisely, you don't have to search for a j for every i. Something
> like this should work for s
@Fenghuang: No. You don't have to search for b for every a, or more
precisely, you don't have to search for a j for every i. Something
like this should work for step 3:
i = 0
j = k-1
repeat while i <= j
if asq[i] + asq[j] < asq[k] then i = i+1
else if asq[i] + asq[j] > asq[k] then j = j-1
should it be O(n^2*lgn)? for each x in n, it's O(n), and for each a,
it'sO(n), and searching b, it's O(lgn), so it's O(n*n*lgn),Thank You!
On Wed, Dec 1, 2010 at 11:02 PM, Senthilnathan Maadasamy <
senthilnathan.maadas...@gmail.com> wrote:
> Hi,
> How about the following approach?
>
> Step
Hi,
How about the following approach?
Step 1: Replace each array element with its square - O(n)
Step 2: Sort the array - O(n*log(n))
Step 3: For each element x in the array
Find two elements a, b in the array (if any) such that
a+b = x.
Since finding
If you store the squares of elements in a hash table, you dont need a binary
search reducing the running time by a factor of log_base2(n)
On Wed, Dec 1, 2010 at 12:50 AM, Akash Agrawal wrote:
> Guys,
>
> I have written a blog post for finding triplets in an integer array A[]
> which satisfy fol
int solve(int lo, int hi) { // lo = 0, and hi = length - 1 in initial pass
if(lo==hi)
return a[lo];
int &d = dp[lo][hi];
if(~d) return d; // dp array initialized with {-1}
d = -INF;
for(int i=lo;i wrote:
> thats right !
> DP must be the best approach to solve
14 matches
Mail list logo
