Dado un número N , hay dos pasos a realizar.
- En un paso impar, XOR el número con cualquier 2^M-1 , donde M es elegido por usted.
- En un paso par, aumente el número en 1 .
Siga realizando los pasos hasta que N se convierta en 2^X-1 (donde x puede ser cualquier número entero). La tarea es imprimir todos los pasos.
Ejemplos:
Entrada: 39
Salida:
Paso 1: Xor con 31
Paso 2: Incrementar en 1 Paso
3: Xor con 7 Paso 4
: Incrementar en 1
Elija M = 5, N se transforma en 39 ^ 31 = 56.
Incremente N en 1 cambiando su valor a N = 57.
Elija M = 3, x se transforma en 57 ^ 7 = 62.
Aumente X en 1, cambiando su valor a 63 = 2^6 – 1.
Entrada: 7
Salida: No se requieren pasos.
Enfoque : Se pueden seguir los siguientes pasos para resolver el problema anterior:
- En cada paso impar, encuentre el bit no establecido más a la izquierda (digamos la posición x en términos de indexación 1) en el número y haga xor con 2^x-1.
- En cada paso par, aumente el número en 1.
- Si en cualquier paso, el número no tiene más bits sin configurar, entonces regrese.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the leftmost
// unset bit in a number.
int find_leftmost_unsetbit(int n)
{
int ind = -1;
int i = 1;
while (n) {
if (!(n & 1))
ind = i;
i++;
n >>= 1;
}
return ind;
}
// Function that perform
// the step
void perform_steps(int n)
{
// Find the leftmost unset bit
int left = find_leftmost_unsetbit(n);
// If the number has no bit
// unset, it means it is in form 2^x -1
if (left == -1) {
cout << "No steps required";
return;
}
// Count the steps
int step = 1;
// Iterate till number is of form 2^x - 1
while (find_leftmost_unsetbit(n) != -1) {
// At even step increase by 1
if (step % 2 == 0) {
n += 1;
cout << "Step" << step << ": Increase by 1\n";
}
// Odd step xor with any 2^m-1
else {
// Find the leftmost unset bit
int m = find_leftmost_unsetbit(n);
// 2^m-1
int num = pow(2, m) - 1;
// Perform the step
n = n ^ num;
cout << "Step" << step
<< ": Xor with " << num << endl;
}
// Increase the steps
step += 1;
}
}
// Driver code
int main()
{
int n = 39;
perform_steps(n);
return 0;
}
Java
// Java program to implement
// the above approach
class GFG
{
// Function to find the leftmost
// unset bit in a number.
static int find_leftmost_unsetbit(int n)
{
int ind = -1;
int i = 1;
while (n > 0)
{
if ((n % 2) != 1)
{
ind = i;
}
i++;
n >>= 1;
}
return ind;
}
// Function that perform
// the step
static void perform_steps(int n)
{
// Find the leftmost unset bit
int left = find_leftmost_unsetbit(n);
// If the number has no bit
// unset, it means it is in form 2^x -1
if (left == -1)
{
System.out.print("No steps required");
return;
}
// Count the steps
int step = 1;
// Iterate till number is of form 2^x - 1
while (find_leftmost_unsetbit(n) != -1)
{
// At even step increase by 1
if (step % 2 == 0)
{
n += 1;
System.out.println("Step" + step + ": Increase by 1");
}
// Odd step xor with any 2^m-1
else
{
// Find the leftmost unset bit
int m = find_leftmost_unsetbit(n);
// 2^m-1
int num = (int) (Math.pow(2, m) - 1);
// Perform the step
n = n ^ num;
System.out.println("Step" + step
+ ": Xor with " + num);
}
// Increase the steps
step += 1;
}
}
// Driver code
public static void main(String[] args)
{
int n = 39;
perform_steps(n);
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 program to implement
# the above approach
# Function to find the leftmost
# unset bit in a number.
def find_leftmost_unsetbit(n):
ind = -1;
i = 1;
while (n):
if ((n % 2) != 1):
ind = i;
i += 1;
n >>= 1;
return ind;
# Function that perform
# the step
def perform_steps(n):
# Find the leftmost unset bit
left = find_leftmost_unsetbit(n);
# If the number has no bit
# unset, it means it is in form 2^x -1
if (left == -1):
print("No steps required");
return;
# Count the steps
step = 1;
# Iterate till number is of form 2^x - 1
while (find_leftmost_unsetbit(n) != -1):
# At even step increase by 1
if (step % 2 == 0):
n += 1;
print("Step" , step ,
": Increase by 1\n");
# Odd step xor with any 2^m-1
else:
# Find the leftmost unset bit
m = find_leftmost_unsetbit(n);
# 2^m-1
num = (2**m) - 1;
# Perform the step
n = n ^ num;
print("Step" , step,
": Xor with" , num );
# Increase the steps
step += 1;
# Driver code
n = 39;
perform_steps(n);
# This code contributed by PrinciRaj1992
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to find the leftmost
// unset bit in a number.
static int find_leftmost_unsetbit(int n)
{
int ind = -1;
int i = 1;
while (n > 0)
{
if ((n % 2) != 1)
{
ind = i;
}
i++;
n >>= 1;
}
return ind;
}
// Function that perform
// the step
static void perform_steps(int n)
{
// Find the leftmost unset bit
int left = find_leftmost_unsetbit(n);
// If the number has no bit
// unset, it means it is in form 2^x -1
if (left == -1)
{
Console.Write("No steps required");
return;
}
// Count the steps
int step = 1;
// Iterate till number is of form 2^x - 1
while (find_leftmost_unsetbit(n) != -1)
{
// At even step increase by 1
if (step % 2 == 0)
{
n += 1;
Console.WriteLine("Step" + step + ": Increase by 1");
}
// Odd step xor with any 2^m-1
else
{
// Find the leftmost unset bit
int m = find_leftmost_unsetbit(n);
// 2^m-1
int num = (int) (Math.Pow(2, m) - 1);
// Perform the step
n = n ^ num;
Console.WriteLine("Step" + step
+ ": Xor with " + num);
}
// Increase the steps
step += 1;
}
}
// Driver code
static public void Main ()
{
int n = 39;
perform_steps(n);
}
}
// This code contributed by ajit.
PHP
<?php
// Php program to implement
// the above approach
// Function to find the leftmost
// unset bit in a number.
function find_leftmost_unsetbit($n)
{
$ind = -1;
$i = 1;
while ($n)
{
if (!($n & 1))
$ind = $i;
$i++;
$n >>= 1;
}
return $ind;
}
// Function that perform
// the step
function perform_steps($n)
{
// Find the leftmost unset bit
$left = find_leftmost_unsetbit($n);
// If the number has no bit
// unset, it means it is in form 2^x -1
if ($left == -1)
{
echo "No steps required";
return;
}
// Count the steps
$step = 1;
// Iterate till number is of form 2^x - 1
while (find_leftmost_unsetbit($n) != -1)
{
// At even step increase by 1
if ($step % 2 == 0)
{
$n += 1;
echo "Step",$step, ": Increase by 1\n";
}
// Odd step xor with any 2^m-1
else
{
// Find the leftmost unset bit
$m = find_leftmost_unsetbit($n);
// 2^m-1
$num = pow(2, $m) - 1;
// Perform the step
$n = $n ^ $num;
echo "Step",$step ,": Xor with ", $num ,"\n";
}
// Increase the steps
$step += 1;
}
}
// Driver code
$n = 39;
perform_steps($n);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find the leftmost
// unset bit in a number.
function find_leftmost_unsetbit(n)
{
let ind = -1;
let i = 1;
while (n) {
if (!(n & 1))
ind = i;
i++;
n >>= 1;
}
return ind;
}
// Function that perform
// the step
function perform_steps(n)
{
// Find the leftmost unset bit
let left = find_leftmost_unsetbit(n);
// If the number has no bit
// unset, it means it is in form 2^x -1
if (left == -1) {
document.write("No steps required");
return;
}
// Count the steps
let step = 1;
// Iterate till number is of form 2^x - 1
while (find_leftmost_unsetbit(n) != -1) {
// At even step increase by 1
if (step % 2 == 0) {
n += 1;
document.write(
"Step" + step + ": Increase by 1<br>"
);
}
// Odd step xor with any 2^m-1
else {
// Find the leftmost unset bit
let m = find_leftmost_unsetbit(n);
// 2^m-1
let num = Math.pow(2, m) - 1;
// Perform the step
n = n ^ num;
document.write("Step" + step
+ ": Xor with " + num + "<br>");
}
// Increase the steps
step += 1;
}
}
// Driver code
let n = 39;
perform_steps(n);
</script>
Producción:
Step1: Xor with 31 Step2: Increase by 1 Step3: Xor with 7 Step4: Increase by 1
Complejidad de tiempo: O(logN*logN), ya que estamos usando un ciclo para atravesar logN tiempos y en cada recorrido estamos llamando a la función find_leftmost_unsetbit que cuesta logN.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.