Find the given sum "total" from the three matrixes algorithm

Question

i was following the this question and i felt that this can be solved in O(NLogN). Below is my algorithm:

 1. Sort list1 , list2, list3 i.e. O(NLogN)
 2. while indexA < size and indexB < size and indexC < size //here size is the array size
     int sum = a1[indexA] + a2[indexB] + a3[indexC]
     if sum < total then choose the minimum value from a1, a2, a3 and increment that index
     if sum > total print total can not be found and return
     if sum == total then print the indexes
    //this is  O(N)

Hence all total O(NLogN). Please tell me about the correctness of the above algo.

EDIT

As Muckle_ewe has explained that this algo will fail in some places so there is no point in further discussing on the algo rather please comment whether the question can be solvable in O(NLogN) if so then algo, thanks?

Can you add some more detail for the question please? Thanks! — lsk, Jul 21 '13 at 00:11
@user1930928 i have the link int the question. Please refer. — Trying, Jul 21 '13 at 00:15
what do you mean by `print total can not be found and return`? — Annie Kim, Jul 21 '13 at 00:16
@AnnieKim He means error out because it's not possible to get an exact match — Rup, Jul 21 '13 at 00:17
@AnnieKim because if you proceed then you will get sum which is more than the expected total. Thanks. — Trying, Jul 21 '13 at 00:17
Oh.. I think `choose the minimum value from a1, a2, a3 and increment that index` is a little dangerous.. — Annie Kim, Jul 21 '13 at 00:18
If you choose the mininum and increase the index..it is somewhat like `greedy`..but I think you may miss some cases. — Annie Kim, Jul 21 '13 at 00:19
@AnnieKim it's basically choose minimum between a1[indexA], a2[indexB], a3[indexC]. — Trying, Jul 21 '13 at 00:19
@Trying yes, I know that..Muckle_ewe gave you an exception which i deeply agree.. — Annie Kim, Jul 21 '13 at 00:22

score 3 · Accepted Answer · answered Jul 21 '13 at 00:19

No that would fail on the

if sum < total then choose the minimum value from a1, a2, a3 and increment that index

line. Consider the following counter example (pseudocode)

list1 = [1, 10]
list2 = [2, 3]
list3 = [3, 4]

Let total be 7, for which the solution would be 1 + 2 + 4 (or 1 + 3 + 3). Let indexA = indexB = indexC = 0. Initial sum is then

list1[0] + list2[0] + list3[0]
1 + 2 + 3 = 6

As this is less than 7, we increase the index which gave the smallest list value, which was indexA as list1[indexA] = 1. Sum is then

list1[1] + list2[0] + list3[0]
10 + 2 + 3 = 15

As this is greater than 7 your algorithm tells us there is no solution

Find the given sum "total" from the three matrixes algorithm

1 Answers1