fork download
copy 
  1. // ==================================================================================
  2. // Problem: Piles of Boxes
  3. // ==================================================================================
  4. // Given an array where each element represents the height of a pile of boxes,
  5. // reduce the height of the largest pile to match the next smaller pile until all
  6. // piles are of equal height. Count the number of operations needed to do so.
  7. //
  8. // Approach:
  9. // - Greedy Approach: At each step, we reduce the largest pile to the next smaller pile.
  10. // - This approach minimizes the number of operations required by always reducing to the next smallest pile.
  11. // - The array is sorted first to efficiently compare adjacent piles.
  12. //
  13. // Time Complexity: O(n log n) — The time complexity is dominated by the sorting step (Arrays.sort(arr)).
  14. // Space Complexity: O(1) — No extra space is used except for a few variables.
  15. //
  16. // By Avinash Sinha
  17. // ==================================================================================
  18.  
  19. import java.util.*;
  20.  
  21. class ideone
  22. {
  23.     public static void main(String[] args) {
  24.         int[] arr = {5, 2, 1}; // Sample input
  25.         System.out.println(pilesOfBoxes(arr)); // Output: 3
  26.     }
  27.  
  28.     public static int pilesOfBoxes(int[] arr) {
  29.         Arrays.sort(arr); // Sort the array in ascending order to facilitate comparison
  30.  
  31.         int n = arr.length;
  32.         int count = 0; // To track the number of operations
  33.         int uniqueHeights = 0; // To track the number of unique heights encountered
  34.  
  35.         // Traverse from the end of the array to the beginning, comparing each element with the previous
  36.         for (int i = n - 1; i > 0; i--) {
  37.             if (arr[i] != arr[i - 1]) {
  38.                 // When we encounter a new unique height, increment the counter for unique heights
  39.                 uniqueHeights++;
  40.  
  41.                 // Add the number of operations needed to reduce the piles above to the new height
  42.                 count += uniqueHeights;
  43.             }
  44.         }
  45.  
  46.         return count; // Return the total number of operations
  47.     }
  48. }
  49.  
  50. /*
  51.  * Dry Run Example:
  52.  * Input: {5, 2, 1}
  53.  * After sorting: {1, 2, 5}
  54.  *
  55.  * First iteration:
  56.  * arr = {1, 2, 2} -> 5 is reduced to 2, count = 1
  57.  *
  58.  * Second iteration:
  59.  * arr = {1, 1, 2} -> 2 is reduced to 1, count = 2
  60.  *
  61.  * Final result: arr = {1, 1, 1}, count = 3
  62.  * Output: 3
  63.  */
  64.  
  65. /*
  66.  * Approach:
  67.  * 1. **Greedy Strategy**: We always reduce the largest pile to the next smaller pile.
  68.  * 2. We use the sorted array to efficiently check for unique heights and count how many operations are needed to make the piles equal.
  69.  * 3. The idea behind the greedy approach is that reducing a pile to match a smaller one minimizes the number of operations required, ensuring an optimal solution.
  70.  * 4. The algorithm counts the unique heights while iterating backward through the sorted array, which gives the total number of operations required to make all piles the same height.
  71.  *
  72.  * Time Complexity: O(n log n)
  73.  * - The sorting step `Arrays.sort(arr)` dominates the time complexity with O(n log n).
  74.  * - The loop runs for n iterations, but since sorting is the most expensive operation, the overall time complexity is O(n log n).
  75.  * Space Complexity: O(1)
  76.  * - No extra space is used for data structures beyond a few variables (`count`, `uniqueHeights`), making the space complexity constant.
  77.  */
  78.  
Success #stdin #stdout 0.07s 54696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/QfMAEa
language:
Java (HotSpot 12)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!