Dado un número entero N , la tarea es encontrar el número de pasos necesarios para reducir el número dado N a 1 realizando las siguientes operaciones:
- Si el número es una potencia de 2 , entonces divide el número por 2 .
- De lo contrario, reste la mayor potencia de 2 menor que N de N .
Ejemplos:
Entrada: N = 2
Salida: 1
Explicación: El número dado se puede reducir a 1 siguiendo los siguientes pasos:
Dividir el número por 2 ya que N es una potencia de 2 que modifica el N a 1.
Por lo tanto, el N se puede reducir a 1 en solo 1 paso.Entrada: N = 7
Salida: 2
Explicación: El número dado se puede reducir a 1 siguiendo los siguientes pasos:
Resta 4 la mayor potencia de 2 menos que N. Después del paso, N se modifica a N = 7-4 = 3.
Resta 2 la mayor potencia de 2 menor que N. Después del paso, N se modifica a N = 3-2 = 1.
Por lo tanto, N se puede reducir a 1 en 2 pasos.
Método 1 –
Enfoque: La idea es calcular recursivamente el número mínimo de pasos requeridos.
- Si el número es una potencia de 2 , entonces solo podemos dividir el número por 2 .
- De lo contrario, podemos restar la mayor potencia de 2 más pequeña que N de N .
- Por lo tanto, usaremos la recursividad para las operaciones siempre que sea válido y devolveremos el número de operaciones.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to check
// if n is power of 2
int highestPowerof2(int n)
{
int p = (int)log2(n);
return (int)pow(2, p);
}
// Utility function to find highest
// power of 2 less than or equal
// to given number
bool isPowerOfTwo(int n)
{
if(n==0)
return false;
return (ceil(log2(n)) == floor(log2(n)));
}
// Recursive function to find
// steps needed to reduce
// a given integer to 1
int reduceToOne(int N)
{
// Base Condition
if(N == 1){
return 0;
}
// If the number is a power of 2
if(isPowerOfTwo(N) == true){
return 1 + reduceToOne(N/2);
}
// Else subtract the greatest
//power of 2 smaller than N
//from N
else{
return 1 + reduceToOne(N - highestPowerof2(N));
}
}
// Driver Code
int main()
{
// Input
int N = 7;
// Function call
cout << reduceToOne(N) << endl;
}
Java
// java program for the above approach
class GFG {
// Utility function to check
// if n is power of 2
static int highestPowerof2(int n)
{
int p = (int)(Math.log(n) / Math.log(2));
return (int)Math.pow(2, p);
}
// Utility function to find highest
// power of 2 less than or equal
// to given number
static boolean isPowerOfTwo(int n)
{
if(n==0)
return false;
return (int)(Math.ceil((Math.log(n) / Math.log(2)))) ==
(int)(Math.floor(((Math.log(n) / Math.log(2)))));
}
// Recursive function to find
// steps needed to reduce
// a given integer to 1
static int reduceToOne(int N)
{
// Base Condition
if(N == 1){
return 0;
}
// If the number is a power of 2
if(isPowerOfTwo(N) == true){
return 1 + reduceToOne(N/2);
}
// Else subtract the greatest
//power of 2 smaller than N
//from N
else{
return 1 + reduceToOne(N - highestPowerof2(N));
}
}
// Driver Code
public static void main(String [] args)
{
// Input
int N = 7;
// Function call
System.out.println(reduceToOne(N));
}
}
// This code is contributed by ihritik
Python
# Python program for the above approach import math # Utility function to check # Log base 2 def Log2(x): if x == 0: return false; return (math.log10(x) / math.log10(2)); # Utility function to check # if x is power of 2 def isPowerOfTwo(n): return (math.ceil(Log2(n)) == math.floor(Log2(n))); # Utility function to find highest # power of 2 less than or equal # to given number def highestPowerof2(n): p = int(math.log(n, 2)); return int(pow(2, p)); # Recursive function to find # steps needed to reduce # a given integer to 1 def reduceToOne(N): # Base Condition if(N == 1): return 0 # If the number is a power of 2 if(isPowerOfTwo(N) == True): return 1 + reduceToOne(N/2) # Else subtract the greatest # power of 2 smaller than N # from N else: return 1 + reduceToOne(N - highestPowerof2(N)) # Driver Code # Input N = 7; #Function call print(reduceToOne(N)) # This code is contributed by Samim Hossain Mondal.
C#
// C# program for the above approach
using System;
class GFG {
// Utility function to check
// if n is power of 2
static int highestPowerof2(int n)
{
int p = (int)(Math.Log(n) / Math.Log(2));
return (int)Math.Pow(2, p);
}
// Utility function to find highest
// power of 2 less than or equal
// to given number
static bool isPowerOfTwo(int n)
{
if(n == 0)
return false;
return (int)(Math.Ceiling((Math.Log(n) / Math.Log(2)))) ==
(int)(Math.Floor(((Math.Log(n) / Math.Log(2)))));
}
// Recursive function to find
// steps needed to reduce
// a given integer to 1
static int reduceToOne(int N)
{
// Base Condition
if(N == 1){
return 0;
}
// If the number is a power of 2
if(isPowerOfTwo(N) == true){
return 1 + reduceToOne(N/2);
}
// Else subtract the greatest
//power of 2 smaller than N
//from N
else{
return 1 + reduceToOne(N - highestPowerof2(N));
}
}
// Driver Code
public static void Main()
{
// Input
int N = 7;
// Function call
Console.Write(reduceToOne(N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript program for the above approach
// Utility function to check
// if n is power of 2
function isPowerOfTwo(n)
{
if (n == 0)
return false;
return parseInt( (Math.ceil((Math.log(n) / Math.log(2))))) == parseInt( (Math.floor(((Math.log(n) / Math.log(2))))));
}
// Utility function to find highest
// power of 2 less than or equal
// to given number
function highestPowerof2(n)
{
let p = parseInt(Math.log(n) / Math.log(2), 10);
return Math.pow(2, p);
}
// Recursive function to find
// steps needed to reduce
// a given integer to 1
function reduceToOne(N)
{
// Base Condition
if(N == 1){
return 0;
}
// If the number is a power of 2
if(isPowerOfTwo(N) == true){
return 1 + reduceToOne(N/2);
}
// Else subtract the greatest
//power of 2 smaller than N
//from N
else{
return 1 + reduceToOne(N - highestPowerof2(N));
}
}
// Driver Code
// Input
let N = 7;
// Function call
document.write(reduceToOne(N));
// This code is contributed by Samim Hossain Mondal
</script>
Producción
2
Método 2 –
Enfoque: El problema dado se puede resolver utilizando operadores bit a bit . Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos res con valor 0 y MSB con valor log 2 (N) para almacenar la cantidad de pasos necesarios para reducir el número a 1 y el bit más significativo de N .
- Iterar mientras N no es igual a 1:
- Comprueba si el número es la potencia de 2 y luego divide N entre 2 .
- De lo contrario, reste la mayor potencia de 2 menos que N de N , es decir, actualice N como N=N-2 MSB .
- Incremente res en 1 y disminuya MSB en 1 .
- Finalmente, imprima res .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find steps needed to
// reduce a given integer to 1
int reduceToOne(int N)
{
// Stores the most
// significant bit of N
int MSB = log2(N);
// Stores the number of steps
// required to reduce N to 1
int res = 0;
// Iterates while N
// is not equal 1
while (N != 1) {
// Increment res by 1
res++;
// If N is power of 2
if (N & (N - 1) == 0) {
// Divide N by 2
N /= 2;
}
// Otherwise
else {
// Subtract 2 ^ MSB
// from N
N -= (1 << MSB);
}
// Decrement MSB by 1
MSB--;
}
// Returns res
return res;
}
// Driver code
int main()
{
// Input
int N = 7;
// Function call
cout << reduceToOne(N) << endl;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
public static int logarithm(int number, int base)
{
int res = (int)(Math.log(number) / Math.log(base));
return res;
}
public static int reduceToOne(int N)
{
// Stores the most
// significant bit of N
int MSB = logarithm(N, 2);
// Stores the number of steps
// required to reduce N to 1
int res = 0;
// Iterates while N
// is not equal 1
while (N != 1) {
// Increment res by 1
res++;
// If N is power of 2
if ((N & (N - 1)) == 0) {
// Divide N by 2
N /= 2;
}
// Otherwise
else {
// Subtract 2 ^ MSB
// from N
N -= (1 << MSB);
}
// Decrement MSB by 1
MSB--;
}
// Returns res
return res;
}
public static void main(String[] args)
{
int N = 7;
int res = reduceToOne(N);
System.out.println(res);
}
}
// This code is contributed by lokeshpotta20.
Python3
# Python program for the above approach import math # Function to find steps needed to # reduce a given integer to 1 def reduceToOne(N): # Stores the most # significant bit of N MSB = math.floor(math.log2(N)) # Stores the number of steps # required to reduce N to 1 res = 0 # Iterates while N # is not equal 1 while (N != 1): # Increment res by 1 res += 1 # If N is power of 2 if (N & (N - 1) == 0): # Divide N by 2 N //= 2 # Otherwise else: # Subtract 2 ^ MSB # from N N -= (1 << MSB) # Decrement MSB by 1 MSB-=1 # Returns res return res # Driver code # Input N = 7 # Function call print(reduceToOne(N)) # This code is contributed by shubham Singh
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find steps needed to
// reduce a given integer to 1
static int reduceToOne(int N)
{
// Stores the most
// significant bit of N
int MSB = (int)(Math.Log(N)/Math.Log(2));
// Stores the number of steps
// required to reduce N to 1
int res = 0;
// Iterates while N
// is not equal 1
while (N != 1) {
// Increment res by 1
res++;
// If N is power of 2
if ((N & (N - 1)) == 0) {
// Divide N by 2
N /= 2;
}
// Otherwise
else {
// Subtract 2 ^ MSB
// from N
N -= (1 << MSB);
}
// Decrement MSB by 1
MSB--;
}
// Returns res
return res;
}
// Driver code
public static void Main()
{
// Input
int N = 7;
// Function call
Console.Write(reduceToOne(N));
}
}
// This code is contributed by bgangwar59.
Javascript
<script>
// JavaScript program for the above approach
function logarithm(number, base)
{
let res = (Math.log(number) / Math.log(base));
return res;
}
function reduceToOne(N)
{
// Stores the most
// significant bit of N
let MSB = logarithm(N, 2);
// Stores the number of steps
// required to reduce N to 1
let res = 0;
// Iterates while N
// is not equal 1
while (N != 1) {
// Increment res by 1
res++;
// If N is power of 2
if ((N & (N - 1)) == 0) {
// Divide N by 2
N /= 2;
}
// Otherwise
else {
// Subtract 2 ^ MSB
// from N
N -= (1 << MSB);
}
// Decrement MSB by 1
MSB--;
}
// Returns res
return res;
}
// Driver Code
let N = 7;
let res = reduceToOne(N);
document.write(res);
</script>
Producción
2
Complejidad de tiempo: O(log(N))
Espacio auxiliar: O(1)