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

By ksharpdabu 2020-01-22 #最少操作

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。

import java.util.*;

public class MakeArrayOdd {

    public static void main(String[] args) {
        int[] arr = {40, 6, 40, 20};
        System.out.println(minOperations(arr));
        int[] arr2 =  {2, 4, 16, 8};
        System.out.println(minOperations(arr2));
        int[] arr3 =  {1, 3, 5, 8};
        System.out.println(minOperations(arr3));
    }

    public static int minOperations(int[] arr) {
        int op = 0;
        //TreeMap默认按自然顺序（数字是按从小到大排序），这里不用Set引用对象，否则没有last方法
        TreeSet<Integer> treeSet = new TreeSet<>();
        //第一遍直接把偶数都放进去，剔除掉已经是奇数的
        for (int t : arr) {
            if (t % 2 == 0) {
                treeSet.add(t);
            }
        }

        while (treeSet.size() > 0) {
            int maxValue = treeSet.last();
            int newValue = maxValue/2;
            //如果操作后的数还是偶数，则放到set中，继续操作
            if (newValue % 2  == 0) {
                treeSet.add(newValue);
            }
            op++;
            treeSet.remove(maxValue);
        }
        return op;
    }



}

输出：

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