Consider an array with N elements and value of all the elements is zero. We can perform following operations on the array.
         1. Incremental operations: Choose 1 element from the array and increment its value by 1.
         2. Doubling operation: Double the values of all the elements of array.
Given an array arr[] of integers of size N. Print the smallest possible number of operations needed to change the original array containing only zeroes to arr[].
Example 1:
Input:
N = 3
arr[] = {16, 16, 16}
Output: 7
Explanation: First apply an incremental 
operation to each element. Then apply the 
doubling operation four times. 
Total number of operations is 3+4 = 7.
Example 2:
Input:
N = 2
arr[] = {2, 3}
Output: 4
Explanation: To get the target array 
from {0, 0}, we first increment both 
elements by 1 (2 operations), then double 
the array (1 operation). Finally increment 
second element (1 more operation). 
Total number of operations is 2+1+1 = 4.
Your Task:
You don't need to read input or print anything. Your task is to complete the function countMinOperations() which takes arr[] and n as input parameters and returns an integer denoting the answer.
Expected Time Complexity: O(N*log(max(Arr[i])))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{4}
1 ≤ arr[i] ≤ 5*10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:

    def countMinOperations(self, arr, n):

        # code here

Solutions:
import math

class Solution:

	def countMinOperations(self, arr, n):
		maxop = 0
		sub = 0
		for i in range(n):
			operations = 0
			while arr[i] != 0:
				if arr[i] % 2 == 0:
					arr[i] = arr[i] // 2
					operations += 1
				else:
					arr[i] = arr[i] - 1
					sub += 1
			maxop = max(maxop, operations)
		return maxop + sub


class Solution:

	def countMinOperations(self, arr, n):
		ans = 0
		add = 0
		for i in range(n):
			double = 0
			while arr[i] > 0:
				if arr[i] % 2:
					arr[i] -= 1
					add += 1
				else:
					arr[i] //= 2
					double += 1
			ans = max(ans, double)
		return ans + add


class Solution:

	def countMinOperations(self, target, n):
		result = 0
		while True:
			zero_count = 0
			i = 0
			while i < n:
				if target[i] & 1 > 0:
					break
				elif target[i] == 0:
					zero_count += 1
				i += 1
			if zero_count == n:
				return result
			if i == n:
				for j in range(n):
					target[j] = target[j] // 2
				result += 1
			for j in range(i, n):
				if target[j] & 1:
					target[j] -= 1
					result += 1


import math

class Solution:

	def countMinOperations(self, arr, n):
		ans = 0
		while True:
			zeroCount = 0
			i = 0
			while i < n:
				if arr[i] & 1:
					break
				if arr[i] == 0:
					zeroCount += 1
				i += 1
			if zeroCount == n:
				return ans
			if i == n:
				for j in range(n):
					arr[j] = arr[j] // 2
				ans += 1
			for j in range(n):
				if arr[j] & 1:
					arr[j] -= 1
					ans += 1


class Solution:

	def countMinOperations(self, arr, n):
		(maxop, sub) = (0, 0)
		for i in range(n):
			opr = 0
			while arr[i] != 0:
				if arr[i] % 2 == 0:
					arr[i] = arr[i] // 2
					opr += 1
				else:
					sub += 1
					arr[i] -= 1
			maxop = max(maxop, opr)
		return maxop + sub


class Solution:

	def countMinOperations(self, a, n):
		ones = 0
		doubles = 0
		for i in range(n):
			x = a[i]
			d = 0
			while x != 0:
				if x % 2 == 0:
					d += 1
					x = x // 2
				else:
					ones += 1
					x -= 1
			doubles = max(d, doubles)
		return ones + doubles


class Solution:

	def countMinOperations(self, arr, n):
		count = 0
		for item in arr:
			count += sum((bitti == '1' for bitti in bin(item)[2:]))
		item = max(arr)
		while item > 1:
			if item % 2:
				item -= 1
			item = item // 2
			count += 1
		return count


class Solution:

	def countMinOperations(self, arr, n):
		z = 0
		ans = 0
		while z != n:
			z = 0
			for i in range(n):
				if arr[i] % 2 != 0:
					ans += 1
					arr[i] -= 1
				if arr[i] == 0:
					z += 1
			for i in range(n):
				arr[i] = arr[i] // 2
			ans += 1
		return ans - 1


class Solution:

	def countMinOperations(self, arr, n):
		arr.sort()
		count = 0
		while arr.count(0) != n:
			for i in range(n):
				if arr[i] % 2 == 1:
					arr[i] = arr[i] - 1
					count = count + 1
			for i in range(n):
				arr[i] = arr[i] // 2
			count = count + 1
		return count - 1


import numpy as np

class Solution:

	def countMinOperations(self, arr, n):
		arr = np.array(arr)
		s = 0
		while np.sum(arr) > 0:
			m = arr % 2 == 1
			s += np.sum(m)
			arr[m] -= 1
			if np.sum(arr) > 0:
				s += 1
				arr = arr // 2
		return s


class Solution:

	def countMinOperations(self, arr, n):
		op = 0
		while True:
			z = 0
			i = 0
			while i < n:
				if arr[i] == 0:
					z += 1
				elif arr[i] % 2 != 0:
					break
				i += 1
			if z == n:
				return op
			if i == n:
				for j in range(n):
					arr[j] = arr[j] // 2
				op += 1
			for j in range(n):
				if arr[j] % 2 == 1:
					arr[j] -= 1
					op += 1


class Solution:

	def countMinOperations(self, arr, n):
		arr.sort()
		ans = 0
		while True:
			for i in range(n - 1, -1, -1):
				if arr[i] % 2 == 1:
					arr[i] -= 1
					ans += 1
				arr[i] //= 2
			if arr[n - 1] == 0:
				break
			ans += 1
		return ans


import math

class Solution:

	def countMinOperations(self, arr, n):
		res = 0
		for a in arr:
			res += bin(a)[2:].count('1')
		res += int(math.log(max(arr), 2))
		return res


class Solution:

	def countMinOperations(self, nums, n):
		inc_count = 0
		double_count = 0
		for i in range(len(nums)):
			temp = 0
			while nums[i] != 0:
				if nums[i] % 2 == 0:
					nums[i] //= 2
					temp += 1
				else:
					nums[i] -= 1
					inc_count += 1
			double_count = max(double_count, temp)
		return double_count + inc_count


class Solution:

	def countMinOperations(self, arr, n):
		res = 0
		while True:
			zc = 0
			i = 0
			while i < n:
				if arr[i] == 0:
					zc += 1
				elif arr[i] & 1 > 0:
					break
				i += 1
			if zc == n:
				return res
			if i == n:
				for k in range(n):
					arr[k] //= 2
				res += 1
			for i in range(n):
				if arr[i] & 1 > 0:
					arr[i] -= 1
					res += 1
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.countMinOperations(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def countMinOperations(self, arr, n):
		res = 0
		while True:
			zeros = 0
			x = 0
			while x < len(arr):
				if arr[x] % 2 != 0:
					break
				elif arr[x] == 0:
					zeros += 1
				x += 1
			if zeros == len(arr):
				return res
			elif x == len(arr):
				for x in range(len(arr)):
					arr[x] //= 2
				res += 1
			for x in range(len(arr)):
				if arr[x] % 2 != 0:
					arr[x] -= 1
					res += 1


class Solution:

	def countMinOperations(self, arr, n):
		ar = [0] * len(arr)
		sub = 0
		m = 0
		for i in range(n):
			temp = 0
			while arr[i] != 0:
				if arr[i] % 2 == 0:
					arr[i] //= 2
					temp += 1
				else:
					sub += 1
					arr[i] -= 1
			m = max(temp, m)
		return m + sub


class Solution:

	def countMinOperations(self, a, n):
		m = 0
		sub = 0
		for i in range(n):
			temp = 0
			while a[i] != 0:
				if a[i] % 2 == 0:
					a[i] = a[i] // 2
					temp += 1
				else:
					sub += 1
					a[i] -= 1
			m = max(m, temp)
		return sub + m


class Solution:

	def countMinOperations(self, arr, n):
		result = 0
		if sum(arr) == 0:
			return 0
		while sum(arr) != 0:
			count = 0
			for i in range(n):
				if arr[i] % 2 != 0:
					arr[i] = arr[i] - 1
					result += 1
					if arr[i] != 0:
						arr[i] = arr[i] // 2
						count += 1
				elif arr[i] != 0:
					arr[i] = arr[i] // 2
					count += 1
			if count != 0:
				result += 1
		return result


class Solution:

	def countMinOperations(self, arr, n):
		count = 0
		while True:
			zero_count = 0
			i = 0
			while i < n:
				if arr[i] & 1 > 0:
					break
				elif arr[i] == 0:
					zero_count += 1
				i += 1
			if zero_count == n:
				return count
			if i == n:
				for j in range(n):
					arr[j] = arr[j] // 2
				count += 1
			for j in range(i, n):
				if arr[j] % 2 != 0:
					arr[j] -= 1
					count += 1


class Solution:

	def countMinOperations(self, arr, n):
		c = 0
		while True:
			c1 = 0
			for i in range(n):
				if arr[i] == 0:
					c1 += 1
			if c1 == n:
				break
			for i in range(n):
				if arr[i] % 2 == 0:
					continue
				else:
					arr[i] -= 1
					c += 1
			c1 = 0
			for i in range(n):
				if arr[i] == 0:
					c1 += 1
			if c1 == n:
				break
			c += 1
			for i in range(n):
				arr[i] = arr[i] // 2
		return c


class Solution:

	def countMinOperations(self, arr, n):
		count = []
		tmp = 0
		for i in range(len(arr)):
			count.append(0)
			while arr[i] != 0:
				if arr[i] % 2 == 0:
					arr[i] = arr[i] / 2
					count[i] += 1
				else:
					arr[i] = arr[i] - 1
					tmp += 1
		return tmp + max(count)


class Solution:

	def countMinOperations(self, arr, n):
		c = 0
		while sum(arr) != 0:
			for i in range(n):
				if arr[i] % 2 != 0:
					arr[i] -= 1
					c += 1
				arr[i] = arr[i] // 2
			c += 1
		return c - 1


class Solution:

	def countMinOperations(self, arr, n):
		steps = 0
		for i in range(n):
			if arr[i] % 2 == 1:
				arr[i] -= 1
				steps += 1
		for j in range(n):
			while arr[j] > 1:
				arr = [num / 2 for num in arr]
				steps += 1
				for i in range(n):
					if arr[i] % 2 == 1:
						arr[i] -= 1
						steps += 1
		for k in range(n):
			if arr[k] != 0:
				steps += 1
		return steps


class Solution:

	def count(self, x):
		(sub, div) = (0, 0)
		while x > 0:
			if x % 2 == 0:
				div += 1
				x //= 2
			else:
				sub += 1
				x -= 1
		return (sub, div)

	def countMinOperations(self, arr, n):
		(res, max_div) = (0, 0)
		for a in arr:
			(sub, div) = self.count(a)
			res += sub
			max_div = max(max_div, div)
		res += max_div
		return res


class Solution:

	def countMinOperations(self, arr, n):
		if not n:
			return -1
		if len(set(arr)) == 1 and 0 in set(arr):
			return 0
		counter = 0
		while True:
			for i in range(n):
				if arr[i] == 0:
					continue
				if arr[i] % 2 != 0:
					arr[i] -= 1
					counter += 1
			if len(set(arr)) == 1 and 0 in set(arr):
				break
			for i in range(n):
				if arr[i] > 0:
					arr[i] = arr[i] / 2
			counter += 1
		return counter


class Solution:

	def countMinOperations(self, arr, n):
		c = 0
		while True:
			for i in range(n):
				if arr[i] % 2 == 1:
					arr[i] -= 1
					c += 1
			if max(arr) == 0:
				break
			for i in range(n):
				if arr[i] != 0 and arr[i] % 2 == 0:
					arr[i] = arr[i] // 2
			c += 1
		return c


class Solution:

	def countMinOperations(self, arr, n):
		result = 0
		while True:
			i = 0
			zero_count = 0
			while i < n:
				if arr[i] % 2 != 0:
					break
				if arr[i] == 0:
					zero_count += 1
				i += 1
			if zero_count == n:
				return result
			if i == n:
				for j in range(n):
					arr[j] = arr[j] // 2
				result += 1
			for k in range(i, n):
				if arr[k] % 2 != 0:
					arr[k] -= 1
					result += 1


class Solution:

	def countMinOperations(self, arr, n):
		ans = 0
		while True:
			odds = 0
			for i in arr:
				if i % 2:
					odds += 1
			ans += odds
			if max(arr) != 1:
				ans += 1
			for i in range(n):
				arr[i] = arr[i] // 2
			if max(arr) == 0:
				return ans


class Solution:

	def countMinOperations(self, arr, n):
		count = 0
		while True:
			f1 = True
			for i in range(n):
				if arr[i] > 1:
					f1 = False
				if arr[i] % 2 != 0:
					arr[i] -= 1
					count += 1
			if f1 == True:
				break
			for i in range(n):
				arr[i] = arr[i] / 2
			count += 1
		return count


class Solution:

	def countMinOperations(self, arr, n):
		incs = 0
		maxdoubles = 0
		for num in arr:
			doubles = 0
			while num > 1:
				if num & 1:
					incs += 1
				doubles += 1
				num >>= 1
			incs += num
			maxdoubles = max(maxdoubles, doubles)
		return incs + maxdoubles


class Solution:

	def countMinOperations(self, arr, n):
		res = 0
		doubles = 0
		for i in range(n):
			ldoubles = 0
			while arr[i]:
				if arr[i] % 2:
					res += arr[i] % 2
					arr[i] -= 1
					if arr[i] == 0:
						continue
				arr[i] //= 2
				ldoubles += 1
			doubles = max(doubles, ldoubles)
		return int(res + doubles)


class Solution:

	def countMinOperations(self, target, n):
		count = 0
		while True:
			zero_count = 0
			i = 0
			while i < n:
				if target[i] == 0:
					zero_count += 1
				elif target[i] % 2 != 0:
					break
				i += 1
			if zero_count == n:
				return count
			if i == n:
				j = 0
				while j < n:
					target[j] = target[j] // 2
					j += 1
				count += 1
			j = 0
			while j < n:
				if target[j] % 2 != 0:
					target[j] = target[j] - 1
					count += 1
				j += 1


class Solution:

	def countMinOperations(self, target, n):
		n = len(target)
		ans = 0
		allEven = 1
		while True:
			numZero = 0
			allEven = 1
			for i in range(n):
				if target[i] == 0:
					numZero += 1
				if target[i] % 2 != 0:
					allEven = 0
			if numZero == n:
				return ans
			if allEven == 1:
				for j in range(n):
					target[j] = target[j] // 2
				ans += 1
			if allEven == 0:
				for j in range(n):
					if target[j] % 2 == 1:
						target[j] -= 1
						ans += 1