Recuento de números que se pueden convertir en potencia de 2 mediante una operación dada

Dada una array arr[] , la tarea es contar los números que se pueden convertir en potencia de 2 con la siguiente operación: 
1 se puede agregar a cualquier elemento como máximo una vez si aún no es una potencia de 2.

Ejemplos: 

Entrada: arr[] = {2, 3, 7, 9, 15} 
Salida: 4 
3, 7 y 15 pueden convertirse en una potencia de 2 sumando 1, y 2 ya es una potencia de 2

Entrada: arr[] = {5, 6, 9, 3, 1} 
Salida: 2 
 

Enfoque: recorra la array y verifique si el elemento actual es una potencia de 2, si lo es, actualice count = count + 1 . Si no es una potencia de 2, busque un elemento mayor, es decir , arr[i] + 1 . Para comprobar si un elemento es una potencia de 2:  

• El método ingenuo es dividir repetidamente el elemento por 2 hasta que dé 0 o 1 como resto. si el resto es 1 , entonces es una potencia de 2, de lo contrario no es una potencia de 2.
• Método eficiente: Si X & (X – 1) = 0 entonces X es una potencia de dos. 
  Digamos, X = 16 = 10000 y X – 1 = 15 = 01111 entonces X & (X – 1) = 10000 & 01111 = 0 es decir , X = 16 es una potencia de 2.

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if x is a power of 2
bool isPowerOfTwo(int x)
{
    if (x == 0)
        return false;
 
    // If x & (x-1) = 0 then x is a power of 2
    if (!(x & (x - 1)))
        return true;
    else
        return false;
}
 
// Function to return the required count
int countNum(int a[], int n)
{
    int count = 0;
 
    for (int i = 0; i < n; i++) {
 
        // If a[i] or (a[i]+1) is a power of 2
        if (isPowerOfTwo(a[i]) || isPowerOfTwo(a[i] + 1))
            count++;
    }
 
    return count;
}
 
// Driver code
int main()
{
    int arr[] = { 5, 6, 9, 3, 1 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << countNum(arr, n);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function that returns true if x is a power of 2
static boolean isPowerOfTwo(int x)
{
    if (x == 0)
        return false;
 
    // If x & (x-1) = 0 then x is a power of 2
    if ((x & (x - 1)) == 0)
        return true;
    else
        return false;
}
 
// Function to return the required count
static int countNum(int a[], int n)
{
    int count = 0;
 
    for (int i = 0; i < n; i++) {
 
        // If a[i] or (a[i]+1) is a power of 2
        if (isPowerOfTwo(a[i]) || isPowerOfTwo(a[i] + 1))
            count++;
    }
 
    return count;
}
 
// Driver code
public static void main(String args[])
{
    int arr[] = { 5, 6, 9, 3, 1 };
 
    int n = arr.length;
 
    System.out.println(countNum(arr, n));
 
}
}
 
// This code is contributed by
// Sahil_Shelangia

# Python 3 implementation of the approach
 
# Function that returns true if x
# is a power of 2
def isPowerOfTwo(x):
    if (x == 0):
        return False
 
    # If x & (x-1) = 0 then x is a power of 2
    if ((x & (x - 1)) == 0):
        return True
    else:
        return False
 
# Function to return the required count
def countNum(a, n):
    count = 0
 
    for i in range(0, n, 1):
         
        # If a[i] or (a[i]+1) is a power of 2
        if (isPowerOfTwo(a[i]) or
            isPowerOfTwo(a[i] + 1)):
            count += 1
 
    return count
 
# Driver code
if __name__ == '__main__':
    arr = [5, 6, 9, 3, 1]
 
    n = len(arr)
 
    print(countNum(arr, n))
 
# This code is contributed by
# Sanjit_Prasad

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function that returns true if x is a power of 2
static bool isPowerOfTwo(int x)
{
    if (x == 0)
        return false;
 
    // If x & (x-1) = 0 then x is a power of 2
    if ((x & (x - 1)) == 0)
        return true;
    else
        return false;
}
 
// Function to return the required count
static int countNum(int[] a, int n)
{
    int count = 0;
 
    for (int i = 0; i < n; i++)
    {
        // If a[i] or (a[i]+1) is a power of 2
        if (isPowerOfTwo(a[i]) || isPowerOfTwo(a[i] + 1))
            count++;
    }
 
    return count;
}
 
// Driver code
public static void Main()
{
    int[] arr = { 5, 6, 9, 3, 1 };
    int n = arr.Length;
    Console.WriteLine(countNum(arr, n));
 
}
}
 
// This code is contributed by
// Mukul Singh

<?php
// PHP implementation of the approach
 
// Function that returns true if x is
// a power of 2
function isPowerOfTwo( $x)
{
    if ($x == 0)
        return false;
 
    // If x & (x-1) = 0 then x is a
    // power of 2
    if (!($x & ($x - 1)))
        return true;
    else
        return false;
}
 
// Function to return the required count
function countNum($a, $n)
{
    $cnt = 0;
 
    for ( $i = 0; $i < $n; $i++)
    {
 
        // If a[i] or (a[i]+1) is a power of 2
        if (isPowerOfTwo($a[$i]) ||
            isPowerOfTwo($a[$i] + 1))
            $cnt++;
    }
 
    return $cnt;
}
 
// Driver Code
$arr = array( 5, 6, 9, 3, 1 );
 
$n = count($arr);
 
echo countNum($arr, $n);
 
// This code is contributed by 29AjayKumar
?>

<script>
 
// Javascript implementation of the approach
     
// Function that returns true if x is a power of 2
function isPowerOfTwo(x)
{
    if (x == 0)
        return false;
   
    // If x & (x-1) = 0 then x is a power of 2
    if ((x & (x - 1)) == 0)
        return true;
    else
        return false;
}
 
// Function to return the required count
function countNum(a, n)
{
    let count = 0;
   
    for(let i = 0; i < n; i++)
    {
         
        // If a[i] or (a[i]+1) is a power of 2
        if (isPowerOfTwo(a[i]) ||
            isPowerOfTwo(a[i] + 1))
            count++;
    }
    return count;
}
 
// Driver code
let arr = [ 5, 6, 9, 3, 1 ];
let n = arr.length;
 
document.write(countNum(arr, n));
 
// This code is contributed by unknown2108
 
</script>

2