Updated_Hacker Rank (Intermediate, Equal)

Dynamic Programming

Divide complex problems into simpler sub-problems.

 

- Tabulation (Bottom-Up) - Iteration(반복문)

: For a large set of inputs  →  Make the results one by one.

   

- Memoization (Top/Deep-Down): Recursion(재귀함수)

 : For a small set of inputs  →  Save each result to use next.

 

[Problem Summary]

▪︎ Each colleague has some chocolates (The number of chocolates each colleague has initially < 1000).

▪︎ How to equalize the number of chocolates that each colleague has by adding (1, 2, 5) chocolates.

+ For each operation, she can give chocolates to all but one colleague.

▪︎ Calculate the minimum number of operations needed so that every colleague has the same number of chocolates.

 

Function Description

func equal(arr: [Int]) -> Int { } // int arr[n]: the integers to equalize.

Returns = int: the minimum number of operations required

Constraints

1 ≤ t ≤ 100

1 ≤ n ≤ 10000

+Input Format

The first line contains an integer t, the number of test cases.

Each test case has 2 lines. (t * test_cases)
- The first line contains an integer n, the number of colleagues (the size of arr).
- The second line contains n space-separated integers, arr[i], the number of pieces of chocolate each colleague has at the start.

 

Sample Input

STDIN       Function
-----       --------
1           t = 1
4           arr[] size n = 4
2 2 3 7     arr =[2, 2, 3, 7]

Sample Output

2

Explanation

Start with [2, 2, 3, 7]
Add 1 to all but the 3rd element [3, 3, 3, 8]
Add 5 to all but the 4th element [8, 8, 8, 8] 

Two operations were required.

 

Sample Input 1

1
3
10 7 12

Sample Output 1

3

Explanation 1

Start with [10, 7, 12]
Add 5 to the first two elements [15, 12, 12]
Add 1 to the last two elements [15, 14, 14]
Add 1 to the last two elements [15, 15, 15]

Three operations were required.

 

*Recurrence relation

---

There are two main ideas to solve this problem.

First, to find out the baseline.

Second, the steps to consider just one or to consider all but one are the same. (like 'Combination' in statistics) (= So, we only need to consider one element per operation and add up each step.)

 

1) The baseline can be a 0, -1, or -2. (from the example) = So the answer will be one of three cases.

2) The distance from every element to the minimum number of the array will be added up.

3) The case which has the shortest distance can be an answer.

/* Swift */
func equal(arr: [Int]) -> Int {
    var answer: Int = Int.max // The number of operations
    let min = arr.min()!
    for base in 0..<3 {
        var tmp = 0
        for e in arr {
            let dist = e - (min - base) // 원소 - (최솟값 - 베이스라인)
            let steps = dist/5 + (dist%5)/2 + (dist%5)%2 // 5, 2, 1 순으로 최대한 적게 분해
            tmp += steps // 거리 합산
        }
        if answer > tmp { // Choose the one of three cases
            answer = tmp
        }
    }
    return answer
}

 

After numerous attempts, I couldn't solve it, so I thought of another way after reading the blog below.

Since I haven't had much practice thinking this way, I think it will be important to see and understand many test cases. Also, It would be great to study mathematics additionally or at least just the statistics part while studying algorithms.

---

 

[References]

https://rohangupta-3817.medium.com/hackerrank-dp-equal-5adc78771571

https://www.geeksforgeeks.org/tabulation-vs-memoization/