I am stuck in this problem for past few days, need some help.↵
We are given an array with `input size(1, 2000)` which consists of **digits(0-9) only**.↵
<br/>↵
↵
We are given a set of pair of digits `(N,M) = {(N1,M1), (N2,M2), (N3,M3), (N4,M4)}` containing exactly `4` elements.↵
↵
In pair `(N, M)`, `N` denotes the digit and `M` corresponds to the minimum need of the number in the array.↵
↵
`Output` is an array that has a `minimum count of each element of N`. We need to make some changes in original array to get the output such that cost is minimized. ↵
↵
Let `C(x, y)` be `cost` of changing number `x` to number `y`, then `C(x, y) = |x-y|`. ↵
Our task is to minimize the total cost of changes.↵
↵
↵
**Input Format**↵
<br/>↵
First line: Consists of the array↵
<br/>↵
Four lines continue each containing pair `(Nx, Mx)` where `xE{1, 2, 3, 4}`↵
<br/>↵
↵
**Output Format**↵
<br/>↵
Total cost of changes.↵
↵
**Example 1:** If an array is `{1, 2, 3, 4, 5}` and `N` values of pair `(N, M)` are `2, 3, 4, 5`. Now lets consider that minimum `one 2`, `zero 3`, `two 4` and `zero 5` are needed in array, the input will be like:↵
↵
↵
`1 2 3 4 5`↵
<br/>↵
`2 1`↵
<br/>↵
`3 0`↵
<br/>↵
`4 2`↵
<br/>↵
`5 0`↵
<br/>↵
↵
Output:↵
<br/>↵
`1` ↵
↵
**Explanation**↵
<br/>↵
We change `5` to `4` and cost becomes `|5-4|` and we get Output array `{1, 2, 3, 4, 4}`↵
↵
↵
**Example 2:** ↵
↵
`1 1 1 5 3 7 7 7 8 9 6 5 4 1 2`↵
<br/>↵
`1 1`↵
<br/>↵
`3 5`↵
<br/>↵
`5 0`↵
<br/>↵
`8 2`↵
<br/>↵
↵
↵
**Explanation**↵
<br/>↵
This means that `minimum one 1 , five 3's, zero 5's and two 8's` should be present in array.↵
<br/>↵
↵
We change `2 to 3`, `4 to 3`, two `5 to 3`. Cost for this change is 6.↵
Then we change `9 to 8` and cost becomes `7`. This is the minimal cost and we get magic array `{1, 1, 1, 3, 3, 7, 7, 7, 8, 8, 6, 5, 3, 1, 3}` ↵
↵
↵
**My Approach** ↵
<br/>↵
My approach to this problem was a `greedy approach` in which I checked the `closest digit` to the given `digit` of `N` and then changed that `digit`.↵
This approach wont work every time. Sometime it would be better to use a `digit` other than the `closest digit` to find `minimum cost` as this closest digit can be used by `other digit` of set `N` for replacement to obtain a `better cost`.↵
↵
**Example for which Approach Fail**↵
↵
`1 1 2 3 4 4 4 7 9 10`↵
<br/>↵
`3 4`↵
<br/>↵
`7 3`↵
<br/>↵
`9 1`↵
<br/>↵
`10 1`↵
<br/>↵
↵
**Explanation:**↵
<br/>↵
In this case if we use `greedy` approach then, for `3` we will change `2` and two `4s` to `3` which is wrong as this step will increase total cost.↵
↵
Minimum cost for this solution is when array changes to `1 3 3 3 3 7 7 7 9 10`↵
ans `output` becomes `10` which by using `greedy-approach` comes out to be `12`.↵
↵
↵
↵
We are given an array with `input size(1, 2000)` which consists of **digits(0-9) only**.↵
<br/>↵
↵
We are given a set of pair of digits `(N,M) = {(N1,M1), (N2,M2), (N3,M3), (N4,M4)}` containing exactly `4` elements.↵
↵
In pair `(N, M)`, `N` denotes the digit and `M` corresponds to the minimum need of the number in the array.↵
↵
`Output` is an array that has a `minimum count of each element of N`. We need to make some changes in original array to get the output such that cost is minimized. ↵
↵
Let `C(x, y)` be `cost` of changing number `x` to number `y`, then `C(x, y) = |x-y|`. ↵
Our task is to minimize the total cost of changes.↵
↵
↵
**Input Format**↵
<br/>↵
First line: Consists of the array↵
<br/>↵
Four lines continue each containing pair `(Nx, Mx)` where `xE{1, 2, 3, 4}`↵
<br/>↵
↵
**Output Format**↵
<br/>↵
Total cost of changes.↵
↵
**Example 1:** If an array is `{1, 2, 3, 4, 5}` and `N` values of pair `(N, M)` are `2, 3, 4, 5`. Now lets consider that minimum `one 2`, `zero 3`, `two 4` and `zero 5` are needed in array, the input will be like:↵
↵
↵
`1 2 3 4 5`↵
<br/>↵
`2 1`↵
<br/>↵
`3 0`↵
<br/>↵
`4 2`↵
<br/>↵
`5 0`↵
<br/>↵
↵
Output:↵
<br/>↵
`1` ↵
↵
**Explanation**↵
<br/>↵
We change `5` to `4` and cost becomes `|5-4|` and we get Output array `{1, 2, 3, 4, 4}`↵
↵
↵
**Example 2:** ↵
↵
`1 1 1 5 3 7 7 7 8 9 6 5 4 1 2`↵
<br/>↵
`1 1`↵
<br/>↵
`3 5`↵
<br/>↵
`5 0`↵
<br/>↵
`8 2`↵
<br/>↵
↵
↵
**Explanation**↵
<br/>↵
This means that `minimum one 1 , five 3's, zero 5's and two 8's` should be present in array.↵
<br/>↵
↵
We change `2 to 3`, `4 to 3`, two `5 to 3`. Cost for this change is 6.↵
Then we change `9 to 8` and cost becomes `7`. This is the minimal cost and we get magic array `{1, 1, 1, 3, 3, 7, 7, 7, 8, 8, 6, 5, 3, 1, 3}` ↵
↵
↵
**My Approach** ↵
<br/>↵
My approach to this problem was a `greedy approach` in which I checked the `closest digit` to the given `digit` of `N` and then changed that `digit`.↵
This approach wont work every time. Sometime it would be better to use a `digit` other than the `closest digit` to find `minimum cost` as this closest digit can be used by `other digit` of set `N` for replacement to obtain a `better cost`.↵
↵
**Example for which Approach Fail**↵
↵
`1 1 2 3 4 4 4 7 9 10`↵
<br/>↵
`3 4`↵
<br/>↵
`7 3`↵
<br/>↵
`9 1`↵
<br/>↵
`10 1`↵
<br/>↵
↵
**Explanation:**↵
<br/>↵
In this case if we use `greedy` approach then, for `3` we will change `2` and two `4s` to `3` which is wrong as this step will increase total cost.↵
↵
Minimum cost for this solution is when array changes to `1 3 3 3 3 7 7 7 9 10`↵
ans `output` becomes `10` which by using `greedy-approach` comes out to be `12`.↵
↵
↵
↵
