Given an array of size n, the task is to find the minimum number of operations required in the array such that the product of all array elements is divisible by nth power of 2. In one operation, you can select any index i and multiply ai by i, you can perform an operation on a particular index at most 1 time. (Follow 1-based indexing)
Examples:
Input: arr[] = { 10, 6, 11 }
Output: 1
Explanation: We can apply operation at index 2.
Input: arr[] = {13, 17, 1, 1 }
Output: -1
Explanation: We can not make the product such that divisible by 2n
Approach: To solve the problem follow the below idea:
We will apply operation till the product of the array is not divisible by 2n and apply operation on that index first which give us maximum 2s.
Illustration:
Lets take an example : arr[] = { 6, 1, 5, 1 }
- The product of the array is 30 which is not divisible by 24 here n=4
- We will apply an operation on index 4 because index 4 gives us maximum 2s than index 1, 2, 3. Then the product of the array becomes 120 which is not divisible by 24
- Then, we will apply an operation on index 2, because index 4 is already operated and index 2 gives a maximum 2 than index 1 and 3.
- Then, the product of the array becomes 240 which is divisible by 24.
- In total, it requires 2 operations to make the product of the array such that it is divisible by 2n.
Below are the steps for the above approach:
- Iterate the array to find how many 2s are present in the array initially.
- Iterate the array from the index from 1 to n and find how many 2s each number has and store the count in a vector say v and sort the vector in descending order because we want a maximum of 2s first.
- Initialize a boolean variable say flag = false.
- If the product of the array is divisible by the nth power of 2. The number of 2s in the product of the array should be greater than n.
- Iterate the vector v,
- Check if count2 >= n, update flag = true, and break the loop.
- Else perform the given operation such that, in minimum operation, we have the maximum number of 2s. In each iteration, add numbers of 2s present in that index stored in the vector v and increase operation by 1.
- Check if flag == true or count2 >= n which means the product if the array is divisible by 2n, returns the number of operations performed.
- If the product of the array is not divisible by 2n, return -1.
Below is the code for the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function to find the minimum operation// required, such that the product of// array is divisible by n-th power of 2int divisibleby(int* arr, int n){ int count2 = 0, temp2 = 0, oper = 0; bool flag = false; vector<int> v; // Finding how many 2s are present // in the array initially // by iterating the whole array for (int i = 0; i < n; i++) { // Till arr[i] is divisible by 2 while (arr[i] % 2 == 0) { // Add +1 to count2 count2 += 1; // Divide arr[i] by 2 arr[i] = arr[i] / 2; } } // Finding how many 2s are we can get // by performing n operations for (int i = 1; i <= n; i++) { int temp = i; // Till i is divisible by 2 while (temp % 2 == 0) { // Add +1 to temp2 temp2 += 1; // Divide i by 2 temp = temp / 2; } // Inserting in vector how many 2s // are present in index i if (temp2 > 0) { v.push_back(temp2); } temp2 = 0; } // Sort the vector in decreasing order, // because we need maximum 2s by // performing minimum operations sort(v.begin(), v.end(), greater<int>()); // Iterating the vector of how many // 2s are present at particular index for (int i = 0; i < v.size(); i++) { // After performing some operation //, product of // the array is divisible by 2^n if (count2 >= n) { flag = true; break; } // perform operation & add 2s // present at that index else { count2 += v[i]; oper += 1; } } // If product if array is // divisible by 2^n if (flag || count2 >= n) { // Then return operation // required return oper; } // If product of array is not // divisible by 2^n Then return -1 return -1;}// Drivers codeint main(){ int arr[] = { 10, 6, 11 }; int n = sizeof(arr) / sizeof(int); // Function call cout << divisibleby(arr, n); return 0;} |
Java
import java.util.*;public class Main { // Function to find the minimum operation // required, such that the product of // array is divisible by n-th power of 2 static int divisibleby(int[] arr, int n) { int count2 = 0, temp2 = 0, oper = 0; boolean flag = false; List<Integer> v = new ArrayList<>(); // Finding how many 2s are present // in the array initially // by iterating the whole array for (int i = 0; i < n; i++) { // Till arr[i] is divisible by 2 while (arr[i] % 2 == 0) { // Add +1 to count2 count2 += 1; // Divide arr[i] by 2 arr[i] = arr[i] / 2; } } // Finding how many 2s are we can get // by performing n operations for (int i = 1; i <= n; i++) { int temp = i; // Till i is divisible by 2 while (temp % 2 == 0) { // Add +1 to temp2 temp2 += 1; // Divide i by 2 temp = temp / 2; } // Inserting in vector how many 2s // are present in index i if (temp2 > 0) { v.add(temp2); } temp2 = 0; } // Sort the vector in decreasing order, // because we need maximum 2s by // performing minimum operations Collections.sort(v, Collections.reverseOrder()); // Iterating the vector of how many // 2s are present at particular index for (int i = 0; i < v.size(); i++) { // After performing some operation //, product of // the array is divisible by 2^n if (count2 >= n) { flag = true; break; } // perform operation & add 2s // present at that index else { count2 += v.get(i); oper += 1; } } // If product if array is // divisible by 2^n if (flag || count2 >= n) { // Then return operation // required return oper; } // If product of array is not // divisible by 2^n Then return -1 return -1; } // Drivers code public static void main(String[] args) { int[] arr = { 10, 6, 11 }; int n = arr.length; // Function call System.out.println(divisibleby(arr, n)); }}//This code is contributed by Akash Jha |
Python3
# Function to find the minimum operation# required, such that the product of# array is divisible by n-th power of 2def divisibleby(arr, n): count2 = 0 temp2 = 0 oper = 0 flag = False v = [] # Finding how many 2s are present # in the array initially # by iterating the whole array for i in range(n): # Till arr[i] is divisible by 2 while arr[i] % 2 == 0: # Add +1 to count2 count2 += 1 # Divide arr[i] by 2 arr[i] //= 2 # Finding how many 2s are we can get # by performing n operations for i in range(1, n+1): temp = i # Till i is divisible by 2 while temp % 2 == 0: # Add +1 to temp2 temp2 += 1 # Divide i by 2 temp //= 2 # Inserting in list how many 2s # are present in index i if temp2 > 0: v.append(temp2) temp2 = 0 # Sort the list in decreasing order, # because we need maximum 2s by # performing minimum operations v.sort(reverse=True) # Iterating the list of how many # 2s are present at particular index for i in range(len(v)): # After performing some operation #, product of # the array is divisible by 2^n if count2 >= n: flag = True break # perform operation & add 2s # present at that index else: count2 += v[i] oper += 1 # If product if array is # divisible by 2^n if flag or count2 >= n: # Then return operation # required return oper # If product of array is not # divisible by 2^n Then return -1 return -1# Drivers codearr = [10, 6, 11]n = len(arr)# Function callprint(divisibleby(arr, n))# This code is contributed by tushar rokade |
C#
using System;using System.Collections.Generic;using System.Linq;public class Program{ // Function to find the minimum operation // required, such that the product of // array is divisible by n-th power of 2 public static int DivisibleBy(int[] arr, int n) { int count2 = 0, temp2 = 0, oper = 0; bool flag = false; List<int> v = new List<int>(); // Finding how many 2s are present // in the array initially // by iterating the whole array for (int i = 0; i < n; i++) { // Till arr[i] is divisible by 2 while (arr[i] % 2 == 0) { // Add +1 to count2 count2 += 1; // Divide arr[i] by 2 arr[i] = arr[i] / 2; } } // Finding how many 2s are we can get // by performing n operations for (int i = 1; i <= n; i++) { int temp = i; // Till i is divisible by 2 while (temp % 2 == 0) { // Add +1 to temp2 temp2 += 1; // Divide i by 2 temp = temp / 2; } // Inserting in list how many 2s // are present in index i if (temp2 > 0) { v.Add(temp2); } temp2 = 0; } // Sort the list in decreasing order, // because we need maximum 2s by // performing minimum operations v = v.OrderByDescending(i => i).ToList(); // Iterating the list of how many // 2s are present at particular index foreach (int i in v) { // After performing some operation //, product of // the array is divisible by 2^n if (count2 >= n) { flag = true; break; } // perform operation & add 2s // present at that index else { count2 += i; oper += 1; } } // If product if array is // divisible by 2^n if (flag || count2 >= n) { // Then return operation // required return oper; } // If product of array is not // divisible by 2^n Then return -1 return -1; } // Drivers code public static void Main() { int[] arr = { 10, 6, 11 }; int n = arr.Length; // Function call Console.WriteLine(DivisibleBy(arr, n)); }} |
Javascript
// Function to find the minimum operation// required, such that the product of// array is divisible by n-th power of 2function divisibleby(arr, n) { let count2 = 0, temp2 = 0, oper = 0; let flag = false; let v = []; // Finding how many 2s are present // in the array initially // by iterating the whole array for (let i = 0; i < n; i++) { // Till arr[i] is divisible by 2 while (arr[i] % 2 == 0) { // Add +1 to count2 count2 += 1; // Divide arr[i] by 2 arr[i] = arr[i] / 2; } } // Finding how many 2s are we can get // by performing n operations for (let i = 1; i <= n; i++) { let temp = i; // Till i is divisible by 2 while (temp % 2 == 0) { // Add +1 to temp2 temp2 += 1; // Divide i by 2 temp = temp / 2; } // Inserting in vector how many 2s // are present in index i if (temp2 > 0) { v.push(temp2); } temp2 = 0; } // Sort the vector in decreasing order, // because we need maximum 2s by // performing minimum operations v.sort(function(a, b) { return b - a }); // Iterating the vector of how many // 2s are present at particular index for (let i = 0; i < v.length; i++) { // After performing some operation //, product of // the array is divisible by 2^n if (count2 >= n) { flag = true; break; } // perform operation & add 2s // present at that index else { count2 += v[i]; oper += 1; } } // If product if array is // divisible by 2^n if (flag || count2 >= n) { // Then return operation // required return oper; } // If product of array is not // divisible by 2^n Then return -1 return -1;}// Driver codelet arr = [10, 6, 11];let n = arr.length;// Function callconsole.log(divisibleby(arr, n));//This code is contributed by Akash Jha |
Output
1
Time Complexity: O(n*log2n)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
