Categories
General

Slow Sums Facebook

Suppose we have a list of N numbers, and repeat the following operation until we’re left with only a single number: Choose any two numbers and replace them with their sum. Moreover, we associate a penalty with each operation equal to the value of the new number, and call the penalty for the entire list as the sum of the penalties of each operation.For example, given the list [1, 2, 3, 4, 5], we could choose 2 and 3 for the first operation, which would transform the list into [1, 5, 4, 5] and incur a penalty of 5. The goal in this problem is to find the highest possible penalty for a given input.Signature: int getTotalTime(int[] arr)Input: An array arr containing N integers, denoting the numbers in the list.Output format: An int representing the highest possible total penalty.Constraints: 1 ≤ N ≤ 10^6 1 ≤ Ai ≤ 10^7, where *Ai denotes the ith initial element of an array. The sum of values of N over all test cases will not exceed 5 * 10^6.Example arr = [4, 2, 1, 3] output = 26First, add 4 + 3 for a penalty of 7. Now the array is [7, 2, 1] Add 7 + 2 for a penalty of 9. Now the array is [9, 1] Add 9 + 1 for a penalty of 10. The penalties sum to 26.


# int1 + int2
  #  [4, 2, 1, 3]
  # [7, 2, 1] penalty 7
  # [9, 1] penalty 7 + 9 = 16
  # 10 penalty 7 + 9 = 16 + 10 = 26
  
  #highest penalty
  
  
  #  [4, 2, 1, 3]
  # [5, 2, 3] penalty 5
  # [7,3] penalty 5 + 7 = 12
  # 10 penalty  5 + 7 = 12 + 10 = 22
  
  function getTotalTime(array $arr) : int 
  {
  $penalty = 0;
    $heap = new SplMaxHeap();
    
    # array(4, 2, 1, 3)
    foreach ($arr as $value) 
    {
      $heap->insert($value);
    }
    #heap  4,3,2,1
    
    
    while ($heap->count() > 1) # count 4; 3
    {
      $int1 = $heap->extract(); # 4 ; 7 ; 9
      $int2 = $heap->extract(); # 3 ; 2 ; 1
      $sum = ($int1 + $int2);   # 7 ; 9 ; 10
      $penalty +=  $sum;         # 7; 7+9=16;16+10 = 26 
      $heap->insert($sum);      # 7,2,1 ; 9,1; 10
    }
    
    return $penalty; #26
}

Leave a Reply