Maximum Score

Problem Statement

Maximum Score Problem Description An interviewer at HackerRank recently came up with an interesting problem for the candidates. Given an array arr of n integers, and an integer k , perform k operations on the array. Start with a score of 0. In one operation: Choose any element. Add its value to the score. Replace the element with the integer ceiling of one-third of its value. For example, if the chosen element is 10, then 10 is added to the score, and 10 is replaced by ceil(10 / 3) = 4 . Find the maximum possible score after k operations. Examples Example 1: Input: n = 5, arr = [20, 4, 3, 1, 9], k = 4 Output: 40 Explanation: One of the optimal ways to perform the operations is as follows: Choose 20, score = 20, ceil(20/3) = 7 . Replace 20 with 7 and arr = [7, 4, 3, 1, 9] . Choose 7, score = 20 + 7 = 27, ceil(7/3) = 3 . Replace 7 with 3 and arr = [3, 4, 3, 1, 9] . Choose 4, score = 27 + 4 = 31, ceil(4/3) = 2 . Replace 4 with 2 and arr = [3, 2, 3, 1, 9] . Choose 9, score = 31 + 9 = 40, c