I need help with finding a way to get the 2 numbers with the highest sum out of 3 values.

Example:

the numbers 9 4 7

It is easy to see that 9 + 7 is the largest sum but how do I do this with a loop?

Preferably an algorithm that works with larger numbers. I am able to do it manually with 3 numbers but with larger numbers it is really inconvenient and I want to be able to solve some bigger problems.

Example:

the numbers 9 4 7

It is easy to see that 9 + 7 is the largest sum but how do I do this with a loop?

Preferably an algorithm that works with larger numbers. I am able to do it manually with 3 numbers but with larger numbers it is really inconvenient and I want to be able to solve some bigger problems.

Last edited on

That makes sense. Do you know any sorting algorithms without using one of the libraries?

closed account (*3qX21hU5*)

Preferably an algorithm that works with larger numbers. I am able to do it manually with 3 numbers but with larger numbers it is really inconvenient and I want to be able to solve some bigger problems. |

3 Numbers you will have no problem with having a efficient sort algorithm, but depending on how large of numbers you are dealing with you might have to use a large number library.

Also you could always use std::sort() in the algorithm header but if you want/need to make your own function you can look into a bubblesort which should work just fine since you are only using 3 numbers.

Or even simpler just create a loop that checks which 2 numbers are the highest.

For really large numbers:

Given two strings of digits representing numbers, like "12345", the larger number will be one of:

1) longer

2) the same length where the first different digit is larger

Examples:

"12345" > "123" (because the first is*longer*)

"4719" > "4709" (because the first different digit is larger -- '1' > '0')

To add the numbers, you only need to carry a single digit, just like in grade-school math. (Start at the ends of the strings, though.)

Good luck!

Given two strings of digits representing numbers, like "12345", the larger number will be one of:

1) longer

2) the same length where the first different digit is larger

Examples:

"12345" > "123" (because the first is

"4719" > "4709" (because the first different digit is larger -- '1' > '0')

To add the numbers, you only need to carry a single digit, just like in grade-school math. (Start at the ends of the strings, though.)

Good luck!

So, for a more generalized problem there is a list with N elements, and you want to use M largest ones.

Sorting is one method, but if M is tiny or very close to N, then it might be more efficient to find the largest ones or remove the smallest ones, respectively.

Sorting is one method, but if M is tiny or very close to N, then it might be more efficient to find the largest ones or remove the smallest ones, respectively.

So, for a more generalized problem there is a list with N elements, and you want to use M largest ones. Sorting is one method, but if M is tiny or very close to N, then it might be more efficient to find the largest ones or remove the smallest ones, respectively. |

Clearly if he is unable to do this on his own then efficiency isn't something he should be worrying about.

Sort the numbers with a sorting algorithm of your choice and add the two largest.

Last edited on

> So, for a more generalized problem there is a list with N elements, and you want to use M largest ones.

The standard way to do this is:

Use a linear time selection algorithm ( the quick select algorithm or the median of medians algorithm) of to select the M^{th} largest - (N-M)^{th} smallest - element. And then partition the sequence with this as the pivot.

http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

The standard way to do this is:

Use a linear time selection algorithm ( the quick select algorithm or the median of medians algorithm) of to select the M

http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

JLBorges wrote: |
---|

Use a linear time selection algorithm ( the quick select algorithm or the median of medians algorithm) of to select the Mth largest - (N-M)th smallest - element. And then partition the sequence with this as the pivot. |

> In C++ you can use nth_element()

Yes. The usual implementation is a quick select.

Followed by

Yes. The usual implementation is a quick select.

Followed by

`std::partition()`

JLBorges wrote: |
---|

Followed by `std::partition()` |

Partially sorts the range [first, last) in ascending order so that all elements in the range [first, nth) are less than those in the range [nth, last). Complexity Linear in std::distance(first, last) on average. |

Last edited on

Topic archived. No new replies allowed.