Marc’s Cakewalk

Cakewalk Algorithm

• 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 i cupcakes so far, after eating a cupcake with c calories he must walk at least 2ⁱ x c miles to maintain his weight.
• For example, if he eats 4 cupcakes with calorie counts in the following order: [2, 7, 8, 1], the miles he will need to walk are (2⁰ * 2) + (2¹ * 7) + (2² * 8) + (2³ * 1) = 2 + 14 + 32 + 8 = 56. This is not the minimum, though, so we need to test other orders of consumption. In this case, our minimum miles is calculated as (2⁰ * 8) + (2¹ * 7) + (2² * 2) + (2³ * 1) = 8 + 14 + 8 + 8 = 38.
• 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.

Input Format

The scanner’s input string has two lines.

• The first line contains an integer n, the number of cupcakes in calorie.
• The second line contains n space-separated integers calorie[i].

Output Format

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

4
 2 7 8 1

38

Explanation

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

package com.hi.techpoints.algorithms;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author elavarasan_pk
 *
 */
public class MarcsCakewalk {

	/** Determine the minimum number of miles Marc must walk to maintain his weight.
	 * @param calorie
	 * @return
	 */
	public static long marcsCakewalk(int[] calorie) {
        Arrays.sort(calorie);
        long sum = 0;
        for(int c = 0;c < calorie.length;c++) {
           long pow = (long)Math.pow(2,c);
           sum = sum + (pow * calorie[calorie.length-1-c]);
        }
        return sum;
    }
	
	public static void main(String[] args) {
		String input = "4 \n" //Input array size.
			      + "2 7 8 1";//Array values.
		Scanner sc = new Scanner(input);
		int N = sc.nextInt();
		int arr[] = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		long result = marcsCakewalk(arr);
		System.out.println(result);
		sc.close();
	}
}