|
Given an array A[] of size N such that every element is a positive power of 2. In one operation, choose a non-empty subsequence of the array and multiply all the elements of the subsequence with any positive integer such that the sum of the array becomes a power of 2. The task is to minimize this operation.
Examples:
Input: S = {4, 8, 4, 32}
Output:
1
5
{4}
Explanation: Choose a subsequence {4} and multiplying it by 5
turns the array into [20, 8, 4, 32], whose sum is 64 = 26.
Hence minimum number of operations required to make
sum of sequence into power of 2 is 1.
Input: S = {2, 2, 4, 8}
Output: 0
Explanation: The array already has a sum 16 which is power of 2.
Approach: The problem can be solved based on the following observation:
Observations:
If the sum of sequence is already power of 2, we need 0 operations.
Otherwise, we can make do itusing exactly one operation.
- Let S be the sum of the sequence. We know that S is not a power of 2. After some number of operations, let us assume that we achieve a sum of 2r.
- S < 2r: This is because, in each operation we multiply some subsequence with a positive integer. This would increase the value of the elements of that subsequence and thus the overall sum.
- This means that we have to increase S at least to 2r such that 2r−1 < S < 2r. For this, we need to add 2r − S to the sequence.
Let M denote the smallest element of the sequence. Then 2r − S is a multiple of M.
To convert S to 2r, we can simply multiply M by (2r − (S − M)) / M. This would take only one operation and make the sum of sequence equal to a power of 2. The chosen subsequence in the operation only consists of M.
Follow the steps mentioned below to implement the idea:
- Check if the sequence is already the power of 2, then the answer is 0.
- Otherwise, we require only 1 operation
- Let S be the sum of the sequence (where S is not a power of 2) and r be the smallest integer such that S < 2r.
- In one operation, we choose the smallest number of the sequence (M) and multiply it with X = 2r − (S − M) / M.
- Print the element whose value is minimum in the array.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
void minOperation(int a[], int n)
{
long sum = 0;
int idx = 0;
long min = INT_MAX;
for (int i = 0; i < n; i++) {
sum += a[i];
if (a[i] < min) {
min = a[i];
idx = i + 1;
}
}
long power = (long)(log(sum) / log(2));
if (sum == (long)pow(2, power)) {
cout<<(0)<<endl;
}
else {
cout<<(1)<<endl;
cout<<((
((long)(pow(2, power + 1) - sum) / min)
+ 1))<<endl;
cout<<(a[idx - 1])<<endl;
}
}
int main()
{
int A[] = { 4, 8, 4, 32 };
int N = sizeof(A) / sizeof(A[0]);
minOperation(A, N);
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
public static void minOperation(int a[], int n)
{
long sum = 0;
int idx = 0;
long min = Long.MAX_VALUE;
for (int i = 0; i < n; i++) {
sum += a[i];
if (a[i] < min) {
min = a[i];
idx = i + 1;
}
}
long power = (long)(Math.log(sum) / Math.log(2));
if (sum == (long)Math.pow(2, power)) {
System.out.println(0);
}
else {
System.out.println(1);
System.out.println((
((long)(Math.pow(2, power + 1) - sum) / min)
+ 1));
System.out.println(a[idx - 1]);
}
}
public static void main(String[] args)
{
int A[] = { 4, 8, 4, 32 };
int N = A.length;
minOperation(A, N);
}
}
|
Python3
import math
def minOperation(a, n):
sum = 0
ind = 0
mini = 200000000000
for i in range(n):
sum += A[i]
if A[i] < mini:
mini = A[i]
ind = i+1
power = int(math.log2(sum))
if sum == pow(2, power):
print("0")
else:
print("1")
print((int(pow(2, power+1))-sum)//mini+1)
print(a[ind-1])
if __name__ == '__main__':
A = [4, 8, 4, 32]
N = len(A)
minOperation(A, N)
|
C#
using System;
public class GFG
{
public static void minOperation(int[] a, int n)
{
long sum = 0;
int idx = 0;
long mini = Int64.MaxValue;
for (int i = 0; i < n; i++) {
sum += a[i];
if (a[i] < mini) {
mini = a[i];
idx = i + 1;
}
}
long power = (long)(Math.Log(sum) / Math.Log(2));
if (sum == (long)Math.Pow(2, power)) {
Console.WriteLine(0);
}
else {
Console.WriteLine(1);
Console.WriteLine(
(((long)(Math.Pow(2, power + 1) - sum)
/ mini)
+ 1));
Console.WriteLine(a[idx - 1]);
}
}
static public void Main()
{
int[] A = { 4, 8, 4, 32 };
int N = A.Length;
minOperation(A, N);
}
}
|
Javascript
<script>
function minOperation(a, n)
{
let sum = 0;
let idx = 0;
let min = Number.MAX_VALUE;
for (let i = 0; i < n; i++) {
sum += a[i];
if (a[i] < min) {
min = a[i];
idx = i + 1;
}
}
let power = Math.floor(Math.log(sum) / Math.log(2));
if (sum == Math.pow(2, power)) {
document.write(0);
}
else {
document.write(1 + "<br/>");
document.write((
Math.floor((Math.pow(2, power + 1) - sum) / min)
+ 1) + "<br/>");
document.write(a[idx - 1] + "<br/>");
}
}
let A = [ 4, 8, 4, 32 ];
let N = A.length;
minOperation(A, N);
/ This code is contributed by sanjoy_62.
</script>
|
Time Complexity: O(N)
Auxiliary Space: O(1)
|
