No, even merge sort is O(n * logn). Since we don't know if the array is sorted, we need to look at each element at least once. Otherwise, we wouldn't be able to tell if the array is sorted. I believe the best that can be done is O(n).

I disagree. An array of the same numbers is sorted, but it is ambiguous what direction it is sorted.

I don't like this solution since I will be recalculating numbers in pascals triangle many times.

Test Cases are locked by CW now, can't fix them.

why a duplicate message?

At least PHP does though :)

Not sure why this isn't the top solution. In my opinion it is much more clear what is happening than using indexOf(e).

Wouldn't it actually be O(2n)? n for filter + n for reduce? Or am I misunderstanding something?

An improvement from O(2n) to O(n) is not that significant in most cases.

This is a very poorly written kata. The description instructs to reverse the digits of the number, however the test cases expect the digits to be sorted and reversed (or perhaps just sorted in descending order?). This is especially an issue since most of the test cases include numbers where the digits are already in sorted in ascending order, giving a false positive for someone who wrote code to reflect the actual instructions. Either change the instructions or change the test cases.

EDIT: After re-reading the description it DOES indicate to have the digits in descending order. However, better test cases should still be written so it does not appear the code is passing except for one test case.

Wow! I just realized that std::setprecision will do the rounding for you... Oh well, you learn something new everyday.

I could have just put:

result << std::fixed << std::setprecision(2) << sum;

Oops, forgot to remove #include's. At first I was trying to do something with an ostringstream and iterator...