[interesting question] find an element which is sum of two other elements

This is a discussion on [interesting question] find an element which is sum of two other elements within the C Programming forums, part of the General Programming Boards category; -------------------------------------------------------------------------------- Hello everyone, I am discussing with my friends about an interesting question about find the maximum element in a ...

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    1,579

    [interesting question] find an element which is sum of two other elements

    --------------------------------------------------------------------------------

    Hello everyone,


    I am discussing with my friends about an interesting question about find the maximum element in a set, which is the sum of two other elements.

    For example, in set [1, 2, 3, 5, 8, 10], the answer is 10 (10 = 8 + 2),
    which is the maximum element we can find, and it is the sum of two
    other elements (8 and 2) in the set.

    Currently, I only have brute-force solution. Sorting the set, which takes O(nlgn) time, then enumerate them one by one to find whether two elements can sum up to the maximum element (if the most maximum element does not meet the condition, move to the second largest one), which takes O(n^2) time, so the total time complexity is O(n^2).

    I am wondering whether any one have better ideas?


    thanks in advance,
    George
    Last edited by George2; 06-09-2006 at 01:41 AM.

  2. #2
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    Are we talking unique elements in the set or can there be duplicates?

    Guess it doesn't matter, in either event, one optimization is to cut the set in half based on the highest value, in your case 10 would cut in half at 5 creating
    [1, 2, 3] and [5,8] then you only pair up elements from the left with elements from the right. (if you allowed duplicated and had for instance 2 fives you'd have to make sure you split the fives since it's the middle number, one in each group)
    Last edited by Darryl; 06-09-2006 at 10:14 AM.

  3. #3
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Isn't that still O(n^2)?
    • Assume that a set is a set, not a multi-set.
    • Let O be the original set of numbers. Let o be the largest element in set O.
    • Let A be the set of numbers less than half of the largest element in O. Let a be an element of set A.
    • Let B be the set of numbers greater than half of the largest element in O. Let b be an element of set B.
    • The number of elements in O is equal to n. The number of elements in A is equal to xn, where x is less than 1. The number of elements in B is equal to (1-x)n.
    • You have to traverse A and B a total of xn * (1-x)n times. That's a polynomial with degree of 2, hence O(n^2).
    You can optimize it by starting at the smallest element in set B and the largest element in set A, traversing set A first. While traversing set A, if a + b is less than o, then you have to increment b to the next element of set B and start over in set A. However, I still think that's O(n^2).

    [edit] Had to redefine a couple of variables.
    Last edited by pianorain; 06-09-2006 at 10:33 AM.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  4. #4
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    But it's still has to be more efficient because it's not even considering certain enumerations such as if 3+2 = 10 where the original idea did ( or at least that's how I understood it).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 09-05-2004, 08:13 AM
  2. Sorting a 2-dimensional array
    By kmoyle73 in forum C++ Programming
    Replies: 3
    Last Post: 05-05-2004, 02:54 PM
  3. Struct *** initialization
    By Saravanan in forum C Programming
    Replies: 20
    Last Post: 10-09-2003, 01:04 PM
  4. Binary searches
    By Prezo in forum C Programming
    Replies: 4
    Last Post: 09-10-2002, 10:54 PM
  5. find the k-th smallest element in O(logk) time
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 10-22-2001, 04:51 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21