Potencias de dos y subsecuencias

Dada una array de tamaño N, encuentre el recuento de subsecuencias que, cuando se multiplican, dan como resultado un número que es una potencia de 2. Ejemplos:

Input : A[] = {1, 2, 3}
Output : 3
Explanation: There are 3 such subsequences {1}, 
{2} and {1, 2}.

Input : A[] = {3, 5, 9}
Output : 0
Explanation: There is no such subsequence.

A partir de las propiedades de la potencia de dos, podemos ver que solo se puede expresar como un producto de números que en sí mismo es potencia de 2. Entonces, primero recorremos la array y contamos el total de números en la array que son potencia de dos. Digamos que hay N de esos números en la array. Podemos elegir 1, 2, 3 o… o N de esos números para obtener una subsecuencia que, cuando se multiplica, da como resultado un número que es una potencia de dos.

Por lo tanto la respuesta requerida será: 

respuesta = 

*** QuickLaTeX cannot compile formula:
 

*** Error message:
Error: Nothing to show, formula is empty

+ 

*** QuickLaTeX cannot compile formula:
 

*** Error message:
Error: Nothing to show, formula is empty

+ … + 

*** QuickLaTeX cannot compile formula:
 

*** Error message:
Error: Nothing to show, formula is empty

respuesta = 

*** QuickLaTeX cannot compile formula:
 

*** Error message:
Error: Nothing to show, formula is empty

A continuación se muestra la implementación de la idea anterior. 

Implementación:

// CPP program to count number of subsequences
// which when multiplied result in a power of 2.
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if num is power of
// two or not.
bool isPowerOf2(int num)
{
    if (num == 0)
        return false;
 
    if (num == 1)
        return true;
 
    if (num & (num - 1))
        return false;
 
    return true;
}
 
// counting all subsequences whose product
// is power of 2.
int countSubsequence(int a[], int size)
{
    int count = 0;
    for (int i = 0; i < size; i++)
        if (isPowerOf2(a[i]))
            count++;
    return (int)(pow(2, count)) - 1;
}
 
// Driver code
int main()
{
    int a[] = { 1, 2, 3 };
    cout << countSubsequence(a, 3) << endl;
    int b[] = { 3, 5, 9 };
    cout << countSubsequence(b, 3) << endl;
    return 0;
}

// JAVA program to count number of
// subsequences which when multiplied
// result in a power of 2.
import java.io.*;
import java.math.*;
 
class GFG {
     
    // Function to check if num is
    // power of two or not.
    static boolean isPowerOf2(int num)
    {
        if (num == 0)
            return false;
      
        if (num == 1)
            return true;
      
        if (num / 2 == (num - 1) / 2)
            return false;
      
        return true;
    }
      
    // counting all subsequences whose
    // product is power of 2.
    static int countSubsequence(int a[],
                                int size)
    {
        int count = 0;
        for (int i = 0; i < size; i++)
            if (isPowerOf2(a[i]))
                count++;
        return (int)(Math.pow(2, count)) - 1;
    }
      
    // Driver
    public static void main(String args[])
    {
        int a[] = { 1, 2, 3 };
        System.out.println(countSubsequence(a, 3));
        int b[] = { 3, 5, 9 };
        System.out.println(countSubsequence(b, 3)) ;
    }
}
 
/*This code is contributed by Nikita Tiwari.*/

# Python program to count number of
# subsequences which when multiplied
# result in a power of 2.
 
# Function to check if num is power
# of two or not.
def isPowerOf2(num) :
    if (num == 0) :
        return False
  
    if (num == 1) :
        return True
  
    if (num & (num - 1)) :
        return False
  
    return True
 
# counting all subsequences whose
# product is power of 2.
def countSubsequence(a, size) :
    count = 0
    for i in range(0,size) :
        if (isPowerOf2(a[i])) :
            count = count + 1
    return (int)(pow(2, count)) - 1
  
# Driver code
a = [ 1, 2, 3 ];
print countSubsequence(a, 3)
b = [ 3, 5, 9 ]
print countSubsequence(b, 3)
 
# This code is contributed by Nikita Tiwari

// C# program to count number of
// subsequences which when multiplied
// result in a power of 2.
using System;
 
class GFG {
     
    // Function to check if num is
    // power of two or not.
    static bool isPowerOf2(int num)
    {
        if (num == 0)
            return false;
     
        if (num == 1)
            return true;
     
        if (num / 2 == (num - 1) / 2)
            return false;
     
        return true;
    }
     
    // counting all subsequences whose
    // product is power of 2.
    static int countSubsequence(int []a,
                                int size)
    {
        int count = 0;
        for (int i = 0; i < size; i++)
            if (isPowerOf2(a[i]))
                count++;
        return (int)(Math.Pow(2, count)) - 1;
    }
     
    // Driver  code
    public static void Main()
    {
        int []a = { 1, 2, 3 };
        Console.WriteLine(countSubsequence(a, 3));
        int []b = { 3, 5, 9 };
        Console.WriteLine(countSubsequence(b, 3)) ;
    }
}
 
/*This code is contributed by vt_m.*/

<?php
// PHP program to count number
// of subsequences which when
// multiplied result in a power
// of 2.
 
// Function to check if num
// is power of  two or not.
function isPowerOf2( $num)
{
    if ($num == 0)
        return false;
 
    if ($num == 1)
        return true;
 
    if ($num & ($num - 1))
        return false;
 
    return true;
}
 
// counting all subsequences whose
// product is power of 2.
function countSubsequence( $a, $size)
{
    $count = 0;
    for($i = 0; $i < $size; $i++)
        if (isPowerOf2($a[$i]))
            $count++;
    return pow(2, $count) - 1;
}
 
    // Driver Code
    $a = array(1, 2, 3);
    echo countSubsequence($a, 3) ,"\n";
    $b = array(3, 5, 9);
    echo countSubsequence($b, 3) ;
 
// This code is contributed by anuj_67.
?>

<script>
    // Javascript program to count number of
    // subsequences which when multiplied
    // result in a power of 2.
     
    // Function to check if num is
    // power of two or not.
    function isPowerOf2(num)
    {
        if (num == 0)
            return false;
       
        if (num == 1)
            return true;
       
        if (parseInt(num / 2, 10) == parseInt((num - 1) / 2, 10))
            return false;
       
        return true;
    }
       
    // counting all subsequences whose
    // product is power of 2.
    function countSubsequence(a, size)
    {
        let count = 0;
        for (let i = 0; i < size; i++)
            if (isPowerOf2(a[i]))
                count++;
        return (Math.pow(2, count)) - 1;
    }
     
    let a = [ 1, 2, 3 ];
    document.write(countSubsequence(a, 3) + "</br>");
    let b = [ 3, 5, 9 ];
    document.write(countSubsequence(b, 3)) ;
     
</script>

3
0

Este artículo es una contribución de ShivamKD . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.