Convierte el entero X dado a la forma 2^N – 1

Posted on by Rudeus Greyrat

Dado un entero x . La tarea es convertir x a la forma 2 n – 1 realizando las siguientes operaciones en el orden especificado en x : 
 

  1. Puede seleccionar cualquier número entero no negativo n y actualizar x = x xor (2 n – 1)
  2. Reemplace x con x + 1 .

La primera operación aplicada debe ser de un primer tipo, la segunda del segundo tipo, la tercera de nuevo del primer tipo, y así sucesivamente. Formalmente, si numeramos las operaciones desde uno en el orden en que se ejecutan, entonces las operaciones impares deben ser del primer tipo y las operaciones pares deben ser del segundo tipo. La tarea es encontrar el número de operaciones requeridas para convertir x a la forma 2 n – 1 . 
Ejemplos: 
 

Entrada: x = 39 
Salida: 4 
Operación 1: Elija n = 5, x se transforma en (39 x o 31) = 56. 
Operación 2: x = 56 + 1 = 57 
Operación 3: Elija n = 3, x se transforma en (57 x o 7) = 62. 
Operación 4: x = 62 + 1 = 63 es decir (2 6 – 1). 
Entonces, el número total de operaciones es 4.
Entrada: x = 7 
Salida: 0 
Como 2 3 -1 = 7. 
Por lo tanto, no se requiere ninguna operación. 
 

Enfoque: tome el número más pequeño mayor que x , que tiene la forma de 2 n – 1, digamos num , luego actualice x = x xor num y luego x = x + 1 realizando dos operaciones. Repita el paso hasta que x sea de la forma 2 n – 1 . Imprime el número de operaciones realizadas al final.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const int MAX = 24;
 
// Function to return the count
// of operations required
int countOp(int x)
{
 
    // To store the powers of 2
    int arr[MAX];
    arr[0] = 1;
    for (int i = 1; i < MAX; i++)
        arr[i] = arr[i - 1] * 2;
 
    // Temporary variable to store x
    int temp = x;
 
    bool flag = true;
 
    // To store the index of
    // smaller number larger than x
    int ans;
 
    // To store the count of operations
    int operations = 0;
 
    bool flag2 = false;
 
    for (int i = 0; i < MAX; i++) {
 
        if (arr[i] - 1 == x)
            flag2 = true;
 
        // Stores the index of number
        // in the form of 2^n - 1
        if (arr[i] > x) {
            ans = i;
            break;
        }
    }
 
    // If x is already in the form
    // 2^n - 1 then no operation is required
    if (flag2)
        return 0;
 
    while (flag) {
 
        // If number is less than x increase the index
        if (arr[ans] < x)
            ans++;
 
        operations++;
 
        // Calculate all the values (x xor 2^n-1)
        // for all possible n
        for (int i = 0; i < MAX; i++) {
            int take = x ^ (arr[i] - 1);
            if (take <= arr[ans] - 1) {
 
                // Only take value which is
                // closer to the number
                if (take > temp)
                    temp = take;
            }
        }
 
        // If number is in the form of 2^n - 1 then break
        if (temp == arr[ans] - 1) {
            flag = false;
            break;
        }
 
        temp++;
        operations++;
        x = temp;
 
        if (x == arr[ans] - 1)
            flag = false;
    }
 
    // Return the count of operations
    // required to obtain the number
    return operations;
}
 
// Driver code
int main()
{
    int x = 39;
 
    cout << countOp(x);
 
    return 0;
}

Java

// Java implementation of the approach
import java.io.*;
 
class GFG
{
 
static int MAX = 24;
 
// Function to return the count
// of operations required
static int countOp(int x)
{
 
    // To store the powers of 2
    int arr[] = new int[MAX];
    arr[0] = 1;
    for (int i = 1; i < MAX; i++)
        arr[i] = arr[i - 1] * 2;
 
    // Temporary variable to store x
    int temp = x;
 
    boolean flag = true;
 
    // To store the index of
    // smaller number larger than x
    int ans =0;
 
    // To store the count of operations
    int operations = 0;
 
    boolean flag2 = false;
 
    for (int i = 0; i < MAX; i++)
    {
 
        if (arr[i] - 1 == x)
            flag2 = true;
 
        // Stores the index of number
        // in the form of 2^n - 1
        if (arr[i] > x)
        {
            ans = i;
            break;
        }
    }
 
    // If x is already in the form
    // 2^n - 1 then no operation is required
    if (flag2)
        return 0;
 
    while (flag)
    {
 
        // If number is less than x increase the index
        if (arr[ans] < x)
            ans++;
 
        operations++;
 
        // Calculate all the values (x xor 2^n-1)
        // for all possible n
        for (int i = 0; i < MAX; i++)
        {
            int take = x ^ (arr[i] - 1);
            if (take <= arr[ans] - 1)
            {
 
                // Only take value which is
                // closer to the number
                if (take > temp)
                    temp = take;
            }
        }
 
        // If number is in the form of 2^n - 1 then break
        if (temp == arr[ans] - 1)
        {
            flag = false;
            break;
        }
 
        temp++;
        operations++;
        x = temp;
 
        if (x == arr[ans] - 1)
            flag = false;
    }
 
    // Return the count of operations
    // required to obtain the number
    return operations;
}
 
    // Driver code
    public static void main (String[] args)
    {
        int x = 39;
        System.out.println(countOp(x));
    }
}
 
// This code is contributed by anuj_67..

Python3

# Python3 implementation of the approach
 
MAX = 24;
 
# Function to return the count
# of operations required
def countOp(x) :
 
    # To store the powers of 2
    arr = [0]*MAX ;
    arr[0] = 1;
    for i in range(1, MAX) :
        arr[i] = arr[i - 1] * 2;
 
    # Temporary variable to store x
    temp = x;
 
    flag = True;
 
    # To store the index of
    # smaller number larger than x
    ans = 0;
 
    # To store the count of operations
    operations = 0;
 
    flag2 = False;
 
    for i in range(MAX) :
 
        if (arr[i] - 1 == x) :
            flag2 = True;
 
        # Stores the index of number
        # in the form of 2^n - 1
        if (arr[i] > x) :
            ans = i;
            break;
     
    # If x is already in the form
    # 2^n - 1 then no operation is required
    if (flag2) :
        return 0;
 
    while (flag) :
 
        # If number is less than x increase the index
        if (arr[ans] < x) :
            ans += 1;
 
        operations += 1;
 
        # Calculate all the values (x xor 2^n-1)
        # for all possible n
        for i in range(MAX) :
            take = x ^ (arr[i] - 1);
             
            if (take <= arr[ans] - 1) :
 
                # Only take value which is
                # closer to the number
                if (take > temp) :
                    temp = take;
 
        # If number is in the form of 2^n - 1 then break
        if (temp == arr[ans] - 1) :
            flag = False;
            break;
 
        temp += 1;
        operations += 1;
        x = temp;
 
        if (x == arr[ans] - 1) :
            flag = False;
 
    # Return the count of operations
    # required to obtain the number
    return operations;
 
 
# Driver code
if __name__ == "__main__" :
 
    x = 39;
 
    print(countOp(x));
 
    # This code is contributed by AnkitRai01

C#

// C# implementation of the approach
using System;
 
class GFG
{
     
static int MAX = 24;
 
// Function to return the count
// of operations required
static int countOp(int x)
{
 
    // To store the powers of 2
    int []arr = new int[MAX];
    arr[0] = 1;
    for (int i = 1; i < MAX; i++)
        arr[i] = arr[i - 1] * 2;
 
    // Temporary variable to store x
    int temp = x;
 
    bool flag = true;
 
    // To store the index of
    // smaller number larger than x
    int ans = 0;
 
    // To store the count of operations
    int operations = 0;
 
    bool flag2 = false;
 
    for (int i = 0; i < MAX; i++)
    {
 
        if (arr[i] - 1 == x)
            flag2 = true;
 
        // Stores the index of number
        // in the form of 2^n - 1
        if (arr[i] > x)
        {
            ans = i;
            break;
        }
    }
 
    // If x is already in the form
    // 2^n - 1 then no operation is required
    if (flag2)
        return 0;
 
    while (flag)
    {
 
        // If number is less than x increase the index
        if (arr[ans] < x)
            ans++;
 
        operations++;
 
        // Calculate all the values (x xor 2^n-1)
        // for all possible n
        for (int i = 0; i < MAX; i++)
        {
            int take = x ^ (arr[i] - 1);
            if (take <= arr[ans] - 1)
            {
 
                // Only take value which is
                // closer to the number
                if (take > temp)
                    temp = take;
            }
        }
 
        // If number is in the form of 2^n - 1 then break
        if (temp == arr[ans] - 1)
        {
            flag = false;
            break;
        }
 
        temp++;
        operations++;
        x = temp;
 
        if (x == arr[ans] - 1)
            flag = false;
    }
 
    // Return the count of operations
    // required to obtain the number
    return operations;
}
 
// Driver code
static public void Main ()
{
     
    int x = 39;
    Console.WriteLine(countOp(x));
}
}
 
// This code is contributed by ajit.

Javascript

<script>
 
// Javascript implementation
// of the approach
 
const MAX = 24;
 
// Function to return the count
// of operations required
function countOp(x)
{
 
    // To store the powers of 2
    let arr = new Array(MAX);
    arr[0] = 1;
    for (let i = 1; i < MAX; i++)
        arr[i] = arr[i - 1] * 2;
 
    // Temporary variable to store x
    let temp = x;
 
    let flag = true;
 
    // To store the index of
    // smaller number larger than x
    let ans;
 
    // To store the count of operations
    let operations = 0;
 
    let flag2 = false;
 
    for (let i = 0; i < MAX; i++) {
 
        if (arr[i] - 1 == x)
            flag2 = true;
 
        // Stores the index of number
        // in the form of 2^n - 1
        if (arr[i] > x) {
            ans = i;
            break;
        }
    }
 
    // If x is already in the form
    // 2^n - 1 then no operation is
    // required
    if (flag2)
        return 0;
 
    while (flag) {
 
        // If number is less than x
        // increase the index
        if (arr[ans] < x)
            ans++;
 
        operations++;
 
        // Calculate all the values
        // (x xor 2^n-1)
        // for all possible n
        for (let i = 0; i < MAX; i++) {
            let take = x ^ (arr[i] - 1);
            if (take <= arr[ans] - 1) {
 
                // Only take value which is
                // closer to the number
                if (take > temp)
                    temp = take;
            }
        }
 
        // If number is in the form of
        // 2^n - 1 then break
        if (temp == arr[ans] - 1) {
            flag = false;
            break;
        }
 
        temp++;
        operations++;
        x = temp;
 
        if (x == arr[ans] - 1)
            flag = false;
    }
 
    // Return the count of operations
    // required to obtain the number
    return operations;
}
 
// Driver code
    let x = 39;
 
    document.write(countOp(x));
 
</script>
Producción: 

4

 

Complejidad de tiempo: O(MAX*N)

Espacio Auxiliar: O(MAX)

Publicación traducida automáticamente

Artículo escrito por ankit_1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *