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. // Best Case:
  9. // - All elements are already equal.
  10. // - Only sorting and one equality check are needed.
  11. // - Time Complexity: O(n log n)
  12. // - Space Complexity: O(1)
  13. //
  14. // Worst Case:
  15. // - Maximum height differences between elements.
  16. // - Sorting once, followed by multiple passes reducing larger piles.
  17. // - Time Complexity: O(n^2)
  18. // - Space Complexity: O(1) — no extra data structures used.
  19. //
  20. // Note: Even if input is taken from the user, space complexity remains O(1)
  21. // as no additional memory is used beyond the required input.
  22. //
  23. // By Avinash Sinha
  24. // ==================================================================================
  25.  
  26.  
  27. import java.util.*;
  28.  
  29.  class Ideone {
  30.     public static void main(String[] args) {
  31.         int[] arr ={4,5,5,2,4};
  32.         System.out.println(pilesOfBoxes(arr)); 
  33.     }
  34.  
  35.     public static int pilesOfBoxes(int[] arr) {
  36.         Arrays.sort(arr); // Sort the array in increasing order
  37.         int n = arr.length;
  38.         int count = 0;
  39.  
  40.         // Continue until all piles are equal
  41.         while (!allEqual(arr)) {
  42.             for (int i = n - 1; i >= 1; i--) {
  43.                 if (arr[i] != arr[i - 1]) {
  44.                     arr[i] = arr[i - 1]; // Reduce the larger pile to match the smaller one
  45.                     count++; // Increment the operation count
  46.                 }
  47.             }
  48.         }
  49.  
  50.         return count; // Return the total number of operations
  51.     }
  52.  
  53.     // Check if all piles are equal
  54.     public static boolean allEqual(int[] arr) {
  55.         for (int i = 1; i < arr.length; i++) {
  56.             if (arr[i] != arr[0]) return false; // If any pile differs, return false
  57.         }
  58.         return true; // Return true if all piles are the same height
  59.     }
  60. }
  61.  
  62. /* Dry Run Example:
  63.    Input: {5, 2, 1}
  64.    After sorting: {1, 2, 5}
  65.  
  66.    First iteration:
  67.    arr = {1, 2, 2} -> 5 is reduced to 2, count = 1
  68.    
  69.    Second iteration:
  70.    arr = {1, 1, 2} -> 2 is reduced to 1, count = 2
  71.    
  72.    Final result: arr = {1, 1, 1}, count = 3
  73.    Output: 3
  74. */
  75.  
  76.  
  77.  
  78.  
Success #stdin #stdout 0.08s 54692KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
6
https://ideone.com/sjZyz4
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!