Marc's Cakewalk HackerRank Solution

Marc's Cakewalk HackerRank Solution
Source : https://www.hackerrank.com/challenges/marcs-cakewalk

Marc loves cupcakes, but he also likes to stay fit. Each cupcake has a calorie count, and Marc can walk a distance to expend those calories. If Marc has eaten cupcakes so far, after eating a cupcake with calories he must walk at least miles to maintain his weight.

For example, if he eats cupcakes with calorie counts in the following order: , the miles he will need to walk are . This is not the minimum, though, so we need to test other orders of consumption. In this case, our minimum miles is calculated as .

Given the individual calorie counts for each of the cupcakes, determine the minimum number of miles Marc must walk to maintain his weight. Note that he can eat the cupcakes in any order.

Function Description

Complete the marcsCakewalk function in the editor below. It should return a long integer that represents the minimum miles necessary.

marcsCakewalk has the following parameter(s):

• calorie: an integer array that represents calorie count for each cupcake

Input Format

The first line contains an integer , the number of cupcakes in .
The second line contains space-separated integers .

Constraints

Output Format

Print a long integer denoting the minimum number of miles Marc must walk to maintain his weight.

Sample Input 0

31 3 2

Sample Output 0

11

Explanation 0

Let's say the number of miles Marc must walk to maintain his weight is . He can minimize by eating the cupcakes in the following order:

1. Eat the cupcake with calories, so .
2. Eat the cupcake with calories, so .
3. Eat the cupcake with calories, so .

We then print the final value of , which is , as our answer.

Sample Input 1

47 4 9 6

Sample Output 1

79

Explanation 1

Source : https://www.hackerrank.com/challenges/marcs-cakewalk

Solution

	// Karthikalapati.blogspot.com
	import java.util.Scanner;
	import java.util.Arrays;
	import java.util.Collections;
	// Algorithm: Eat the largest cupcakes first
	// Is this a Greedy Algorithm? No.
	//
	// A greedy algorithm makes the "locally optimal choice at each stage with the hope of finding a
	// global optimum" - Wikipedia. Our solution actually makes the locally LEAST optimal choice at
	// each stage, so it is not a greedy algorithm. Is there a name for this approach? I'm not sure,
	// but maybe we can call it a "reverse-greedy algorithm"
	// Time Complexity: O(n log n)
	public class Solution {
	public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int n = scan.nextInt();
	Integer [] calories = new Integer[n]; // Use Integer instead of int to make sorting in simpler
	for (int i = 0; i < n; i++){
	calories[i] = scan.nextInt();
	}
	scan.close();
	System.out.println(minimumMiles(calories));
	}
	private static long minimumMiles(Integer [] calories) {
	Arrays.sort(calories, Collections.reverseOrder());
	long multiplier = 1;
	long miles = 0;
	for (int j = 0; j < calories.length; j++) {
	miles += calories[j] * multiplier;
	multiplier *= 2;
	}
	return miles;
	}
	}