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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
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
转载请注明：大步's Blog » Make all the array elements odd with minimum operations of given type