# [algorithm learning] LCP 06 Take coins (Java / C / C + + / Python / go / trust)

2022-01-30 23:50:21

This is my participation 11 The fourth of the yuegengwen challenge 2 God , Check out the activity details ：2021 One last more challenge

Thank you very much for reading this article ~ welcome 【 give the thumbs-up 】【 Collection 】【 Comment on 】~ It's not hard to give up , But persistence must be cool ~ I hope all of us can make a little progress every day ~ This paper is written by The white hat of the second leader https://juejin.cn/user/2771185768884824/posts Original blog ~

# LCP 06. Take the coin ：

It's on the table `n` Money is deducted from the pile , The number of each heap is stored in the array `coins` in . We can choose any pile at a time , Take one or two of them , Ask for the minimum number of times to deduct money from all efforts .

# Examples 1

`````` Input ：
[4,2,1]

Output ：
4

explain ：
The first pile of force deduction coins needs to take at least  2  Time , The second pile needs at least  1  Time , The third pile needs at least  1  Time , in total  4  You can get it all at once .
Copy code ``````

# Examples 2

`````` Input ：
[2,3,10]

Output ：
8
Copy code ``````

# Tips

• 1 <= n <= 4
• 1 <= coins[i] <= 10

# analysis

• This algorithm problem two is in charge. I believe everyone can do it , But it has been carefully optimized ？
• Pick one at a time , Obviously, each pile does not affect each other , So it is the desired result to accumulate and calculate the sum of at least several times for each pile .
• You can take one or two at a time , Children also know how to take more , It must be the fastest to take two at a time , But if a pile of coins is odd , Then you can only take one at the last time .
• Direct division 2 Words , Odd numbers will be counted less once , So we need to judge odd or even , If it's an odd number, count it again .
• Can we handle odd and even numbers in a unified way ？ You can directly add and divide again and again to two `(coins[i] + 1) / 2`. If it was even , Then it does not affect the division by 2 Result , If it is an odd number, it will divide the whole by 2 Add one... To the result .
• Bit operations are faster than arithmetic operations , So we can optimize it to `(coins[i] + 1) >> 1`.

## java

``````class Solution {
public int minCount(int[] coins) {
int ans = 0;
for (int c : coins) {
ans += (c + 1) >> 1;
}
return ans;
}
}
Copy code ``````

## c

``````int minCount(int* coins, int coinsSize){
int ans = 0;
for (int i = 0; i < coinsSize; ++i) {
ans += (coins[i] + 1) >> 1;
}
return ans;
}
Copy code ``````

## c++

``````class Solution {
public:
int minCount(vector<int>& coins) {
int ans = 0;
for (int& c : coins) {
ans += (c + 1) >> 1;
}
return ans;
}
};
Copy code ``````

## python

``````class Solution:
def minCount(self, coins: List[int]) -> int:
return sum([(c + 1) >> 1 for c in coins])
Copy code ``````

## go

``````func minCount(coins []int) int {
ans := 0
for _, c := range coins {
ans += (c + 1) >> 1
}
return ans
}
Copy code ``````

## rust

``````impl Solution {
pub fn min_count(coins: Vec<i32>) -> i32 {
coins.iter().map(|c|{
(c + 1) >> 1
}).sum()
}
}
Copy code `````` 