Slaunger Python 3
Two-liner
input() print(sum(c * 2 ** j for (j, c) in enumerate(sorted(map(int, input().split()), reverse=True))))
NicolasBi You can one-line this beauty like this :
input(), print(sum(c * 2 ** j for (j, c) in enumerate(sorted(map(int, input().split()), reverse=True))))
Slaunger But it is an odd construction to use a tuple just to avoid a newline and a bit harder to understand. It is not a goal in itself to make one-liners IMO.
codertoaster But it's good enough to make us non-python programmers jealous lol.
KVS123 could you pls explain what reverse = True does
Slaunger sorted(iterable, reverse=True) iterates over the elements in iterable in reverse sorting order. That is, in descending order.
For instance (python 3)
print(list(sorted([1, 3, 5, 2], reverse=True)))
gives
[5, 3, 2, 1]
whereas
print(list(sorted([1, 3, 5, 2])))
gives
[1, 2, 3, 5]
KVS123 Thank you :)
mike_holcomb Using Horner's method in the lamda to avoid the repeated calls to power function.
from functools import reduce input() print(reduce(lambda x, y: 2*x + y, sorted(map(int, input().split()))))
luumanhlapdi :D
return sum(sorted(calorie)[::-1][i] *2**i for i in range(len(calorie)))
vasukapil2196 why is the problem in greedy algorithm section? Basically i want to ask how to figure out if it is a greedy algorithm.
combinatorial_p1 [deleted]
ggorlen It's greedy because at every step, always choosing the local highest calorie amount will yield the globally optimal solution.
coolash123 can you explain what do you mean by local highest?
alfonso_delamor1 C++ Solution
long marcsCakewalk(vector<int> calorie) { sort(calorie.begin(), calorie.end(), greater<int>()); int exponent = 0; long result = 0; for(int i : calorie) result = result + (i * pow(2, exponent++)); return result; }
raffaele_provin1 Done the same in php. Thought it was the fastest way
vldvel One-liner JavaScript
calorie.sort((p,c) => c - p).reduce((p,c,i) => p + c * Math.pow(2, i), 0)
joserico1 MY Python3 solution:
def marcsCakewalk(calorie): calorie.sort(reverse = True) return sum((2**i)*c for i,c in enumerate(calorie))
gmango I was wondering about the greedy vs non-greedy approach too.
I think that if you want to use the greedy solution, you can sort then:
W[j] = min(W[j-1] + 2^(j-1) * C[j-1], C[j-1] + W[j-1] * 2)W(0) = 0The idea being that you are either eating your cupcake last, or eating it first. The ordering of the sort shouldn't matter.
The non-greedy interpretation is that
W[j]= W[j] + 2^(j-1) * C[j-1]That's thesum += 2**(j-1) * C[j-1]solution.One can prove that
W[j] = W[j-1]+ 2^(j-1) * C[j-1]by induction, but I needed to assume thatC[j] > 0forall j, and thatC[j] >= C[j-1](that the list is sorted in ascending order)
chanakauomfit My java Solution
static long marcsCakewalk(int[] calorie) {
// Complete this function Arrays.sort(calorie); int l=calorie.length; int j=0; long miles=0; for(int i=(l-1);i>=0;i--){ miles=miles+(long)(calorie[i]*Math.pow(2,j)); j++; } return miles; }codertoaster [deleted]
aishwaryabhishe1 Can anyone explain to me why the descending order of array results in lowest calories??
patrick_zebing_1 Because as you eat more cupcakes the 2 to the power of j multiplier becomes larger. If you start larger you end up multiplying the large numbers by smaller 2 power j values minimizing the miles.
grbknr1996 not passing testcase 2 and 3 ,can anyone help me ...thanks in advance.
import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] calories = new int[n]; for(int calories_i=0; calories_i < n; calories_i++){ calories[calories_i] = in.nextInt(); } // your code goes here //sorting of calories[] for(int i =0;i<calories.length-1;i++) { for(int j=0;j<calories.length-1-i;j++) { if(calories[j]<calories[j+1]) { int temp=calories[j]; calories[j]=calories[j+1]; calories[j+1]=temp; } } } double already=0; double sum=0; for(int i=0;i<calories.length;i++) { sum=sum+((double)calories[i]*Math.pow(2,already)); already++; } System.out.println((int)sum); }} `
ka2566 I have a similar issue with test cases 2 & 3 (though coding in C++), would anyone know what makes these cases different?
Thanks!
ashutoshpedneka1 The input format requires the second line to be n space seperated numbers. But the test cases two and three both have less than n numbers. Maybe that's why our code fails, because we do cin till n, but there are no inputs. A try catch block may help.
mathias07 return long type not int
kirtikedia_kk Thanks
aesthetic_boy use long long int , it might pass the cases
ramnarayanan51 Try not to use any sorting algorithm . Use inbuilt sort functions.
rahmanole_bd [deleted]rahmanole_bd Arrays.sort(calorie); long sum = 0; int len = calorie.length-1; for(int i = 0;i
vinay_Chap 40 819 701 578 403 50 400 983 665 510 523 696 532 51 449 333 234 958 460 277 347 950 53 123 227 646 190 938 61 409 110 61 178 659 989 625 237 944 550 954 439
this is the input for test case 2...the array size is 40 and the inputs are 42...the question is wrong...Hope it helps...
spyely [deleted]
narutoitachi329 [deleted]Shubhamgupta1991 i declared my datatype variables as long long int in c++ a it was passing my all test cases
dl0pezaguay0 Python 3:
calorie.sort(reverse=True) return sum([2**i * calorie[i] for i in range(len(calorie))])
Sort 154 Discussions, By:
Please Login in order to post a comment