Minimizar los giros dados requeridos para reducir N a 0

Dado un número entero N , la tarea es reducir el valor de N a 0 realizando las siguientes operaciones un número mínimo de veces:

• Voltee el bit más a la derecha (0 ^th ) en la representación binaria de N .
• Si (i – 1) ^th bit está establecido, cambie el i ^th bit y borre todos los bits desde (i – 2) ^th hasta 0 ^th bit.

Ejemplos:

Entrada: N = 3 
Salida: 2 
Explicación: 
La representación binaria de N (= 3) es 11 
Dado que se establece ^el bit 0 en la representación binaria de N (= 3), cambiar el bit 1 ^de la representación binaria de N modifica N a 1(01). 
Voltear el bit más a la derecha de la representación binaria de N(=1) modifica N a 0(00). 
Por lo tanto, la salida requerida es 2

Entrada: N = 4 
Salida: 7

Enfoque: El problema se puede resolver con base en las siguientes observaciones:

1 -> 0 => 1 
10 -> 11 -> 01 -> 00 => 2 + 1 = 3 
100 -> 101 -> 111 -> 110 -> 010 – > … => 4 + 2 + 1 = 7 
1000 -> 1001 -> 1011 -> 1010 -> 1110 -> 1111 -> 1101 -> 1100 -> 0100 -> … => 8 + 7 = 15 
Por lo tanto, para N = 2 ^N total (2 ^{(N + 1)} – 1) operaciones requeridas.
Si N no es una potencia de 2, entonces la relación de recurrencia es: 
MinOp(N) = MinOp((1 << cntBit) – 1) – MinOp(N – (1 << (cntBit – 1)))
cntBit = total recuento de bits en representación binaria de N. 
MinOp(N) indica el recuento mínimo de operaciones necesarias para reducir N a 0. 
 

Siga los pasos a continuación para resolver el problema:

• Calcule el recuento de bits en representación binaria de N utilizando log ₂ (N) + 1 .
• Utilice la relación de recurrencia anterior y calcule el recuento mínimo de operaciones necesarias para reducir N a 0 .

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

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum count of
// operations required to Reduce N to 0
int MinOp(int N)
{
 
    if (N <= 1)
        return N;
 
    // Stores count of
    // bits in N
    int bit = log2(N) + 1;
 
    // Recurrence relation
    return ((1 << bit) - 1)
           - MinOp(N - (1 << (bit - 1)));
}
 
// Driver Code
int main()
{
 
    int N = 4;
    cout << MinOp(N);
    return 0;
}

// Java program to implement
// the above approach
class GFG{
     
// Function to find the minimum count of
// operations required to Reduce N to 0
public static int MinOp(int N)
{
    if (N <= 1)
        return N;
   
    // Stores count of
    // bits in N
    int bit = (int)(Math.log(N) /
                    Math.log(2)) + 1;
   
    // Recurrence relation
    return ((1 << bit) - 1) - MinOp(
        N - (1 << (bit - 1)));
}
 
// Driver code
public static void main(String[] args)
{
    int N = 4;
     
    System.out.println(MinOp(N));
}
}
 
// This code is contributed by divyeshrabadiya07

# Python program to implement
# the above approach
 
# Function to find the minimum count of
# operations required to Reduce N to 0
import math
def MinOp(N):
    if (N <= 1):
        return N;
 
    # Stores count of
    # bits in N
    bit = (int)(math.log(N) / math.log(2)) + 1;
 
    # Recurrence relation
    return ((1 << bit) - 1) - MinOp(N - (1 << (bit - 1)));
 
# Driver code
if __name__ == '__main__':
    N = 4;
 
    print(MinOp(N));
 
# This code is contributed by 29AjayKumar

// C# program to implement
// the above approach 
using System;
 
class GFG{
     
// Function to find the minimum count of
// operations required to Reduce N to 0
public static int MinOp(int N)
{
    if (N <= 1)
        return N;
         
    // Stores count of
    // bits in N
    int bit = (int)(Math.Log(N) /
                    Math.Log(2)) + 1;
                     
    // Recurrence relation
    return ((1 << bit) - 1) - MinOp(
        N - (1 << (bit - 1)));
}
  
// Driver code
public static void Main()
{
    int N = 4;
     
    Console.WriteLine(MinOp(N));
}
}
 
// This code is contributed by sanjoy_62

<script>
// javascript program to implement
// the above approach
 
// Function to find the minimum count of
// operations required to Reduce N to 0
function MinOp(N)
{
    if (N <= 1)
        return N;
    
    // Stores count of
    // bits in N
    let bit = (Math.log(N) /
                    Math.log(2)) + 1;
    
    // Recurrence relation
    return ((1 << bit) - 1) - MinOp(
        N - (1 << (bit - 1)));
}
 
// Driver code
    let N = 4;
    document.write(MinOp(N));
     
    // This code is contributed by souravghosh0416.
</script>

7

Complejidad de tiempo: O(log(N))  
Espacio auxiliar: O(1)