Marc's Cakewalk

  • + 0 comments

    My Java solution with o(n log n) time complexity and o(1) space complexity:

    public static long marcsCakewalk(List<Integer> calorie) {
            // Sort the calorie array in descending order
            Collections.sort(calorie, Collections.reverseOrder());
            
            // Calculate the total miles to walk using powers of 2 (bit-shifting)
            long totalMiles = 0;
            for (int i = 0; i < calorie.size(); i++) {
                long currentMilesToWalk = (1L << i) * calorie.get(i); // More efficient power of 2 calculation
                totalMiles += currentMilesToWalk;
            }
            
            return totalMiles;
        }