最新消息:

Make all the array elements odd with minimum operations of given type

算法 ksharpdabu 2134浏览 0评论

 

Make all the array elements odd with minimum operations of given type

Given an array arr[] consisting of even integers. At each move, you can select any even number X from the array and divide all the occurrences of X by 2. The task is to find the minimum number of moves needed so that all the elements in the array become odd.

Examples:

Input: arr[] = {40, 6, 40, 20}
Output: 4
Move 1: Select 40 and divide all the occurences
of 40 by 2 to get {20, 6, 20, 20}
Move 2: Select 20 and divide all the occurences
of 20 by 2 to get {10, 6, 10, 10}
Move 3: Select 10 and divide all the occurences
of 10 by 2 to get {5, 6, 5, 5}.
Move 4: Select 6 and divide it by 2 to get {5, 3, 5, 5}.

Input: arr[] = {2, 4, 16, 8}
Output: 4

 

思路:因为元素有大有小,可能一个大的元素除以2后,与其他小的元素一样了,这样下次操作就可以直接一起进行,就可以减少操作的次数。
注意:
1.多个大小相同的偶数元素,我们只要当作一个操作就可以了。同时,我们可以直接忽略数组中已有的奇数,则 [40,40,2]的操作数与[40]是一样的。所以可以把数组的所有偶数元素放到Set中。
2.这里每次操作的都是当前最大的偶数,所以我们需要一个集合来维持排序,Java里可以直接使用TreeSet。

 

 

输出:

4
4
3

 

原文:https://www.geeksforgeeks.org/make-all-the-array-elements-odd-with-minimum-operations-of-given-type/?utm_source=feedburner&utm_medium=email&utm_campaign=Feed%3A+Geeksforgeeks+%28GeeksforGeeks%29

 

转载请注明:大步's Blog » Make all the array elements odd with minimum operations of given type

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址