See the original problem on HackerRank.
Solutions
This easy problem can be solved by first sorting the calories in decreasing order:
1
2
3
4
5
6
7
8
9
10
|
long long n; cin >> n;
vector<int> v(n);
copy_n(istream_iterator<int>(cin), n, begin(v));
sort(begin(v), end(v), greater<>{});
auto miles = 0ll;
for (auto i=0; i<n; ++i)
{
miles += v[i] * (1ll<<i);
}
cout << miles;
|
The zip | map | reduce pattern emerges from the code: conceptually, it’s like zipping each calory with the ith power of 2, mapping the pair with product and summing along the way:
1
2
3
4
5
6
|
long long n; cin >> n;
vector<long long> v(n), twos(n, 2); twos.front() = 1;
copy_n(istream_iterator<int>(cin), n, begin(v));
partial_sum(begin(twos), end(twos), begin(twos), multiplies<>{});
sort(begin(v), end(v), greater<>{});
cout << inner_product(begin(v), end(v), begin(twos), 0ll, plus<>{}, multiplies<>{});
|
partial_sum
used this way generates the first n
powers of 2.
Using C++ ranges (actually, some functionals are not yet in C++20 - however, you can test them using the range-v3 library):
1
2
3
4
5
6
|
long long n; cin >> n;
vector<long long> v(n);
copy_n(istream_iterator<int>(cin), n, begin(v));
sort(v, std::greater<>{});
auto twos = views::partial_sum(views::concat(views::single(1ll), views::repeat_n(2ll, n-1)), std::multiplies<>{});
std::cout << accumulate(views::zip_with(std::multiplies<>{}, v, twos), 0ll);
|
Similar approach in Python:
1
2
|
input()
print(sum(c * 2 ** j for (j, c) in enumerate(sorted(map(int, input().split()), reverse=True))))
|
Javascript one-liner:
1
|
calorie.sort((p,c) => c - p).reduce((p,c,i) => p + c * Math.pow(2, i), 0)
|