Pasos mínimos para llegar al N-ésimo escalón en saltos de potencia perfecta de 2

Dadas N escaleras, la tarea es encontrar el número mínimo de saltos de potencia perfecta de 2 necesarios para llegar a la N-ésima escalera.

Ejemplos: 

Entrada: N = 5 
Salida:  
Explicación: 
Podemos dar saltos de 0->4->5.
Entonces los saltos mínimos requeridos son 2.

Entrada: N = 23 
Salida:
Explicación: 
Podemos dar saltos de 0->1->3->7->23
Entonces los saltos mínimos requeridos son 4. 
 

Primer enfoque: dado que se requiere que los saltos estén en potencia perfecta de 2. Entonces, el conteo de bits establecidos en el número N dado es el número mínimo de saltos requeridos para llegar a Nth escalera como la suma de 2 i para todos los índices de bits establecidos i es igual a N.

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 count the number of jumps
// required to reach Nth stairs.
int stepRequired(int N)
{
 
    int cnt = 0;
 
    // Till N becomes 0
    while (N) {
 
        // Removes the set bits from
        // the right to left
        N = N & (N - 1);
        cnt++;
    }
 
    return cnt;
}
 
// Driver Code
int main()
{
 
    // Number of stairs
    int N = 23;
 
    // Function Call
    cout << stepRequired(N);
    return 0;
}

Java

// Java program for the above approach
 
import java.util.*;
 
class GFG{
 
// Function to count the number of jumps
// required to reach Nth stairs.
static int stepRequired(int N)
{
 
    int cnt = 0;
 
    // Till N becomes 0
    while (N > 0) {
 
        // Removes the set bits from
        // the right to left
        N = N & (N - 1);
        cnt++;
    }
 
    return cnt;
}
 
// Driver Code
public static void main(String[] args)
{
 
    // Number of stairs
    int N = 23;
 
    // Function Call
    System.out.print(stepRequired(N));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 program for the above approach
 
# Function to count the number of jumps
# required to reach Nth stairs.
def stepRequired(N):
 
    cnt = 0;
 
    # Till N becomes 0
    while (N > 0):
 
        # Removes the set bits from
        # the right to left
        N = N & (N - 1);
        cnt += 1;
    return cnt;
 
# Driver Code
if __name__ == '__main__':
 
    # Number of stairs
    N = 23;
 
    # Function Call
    print(stepRequired(N));
     
# This code is contributed by 29AjayKumar

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to count the number of
// jumps required to reach Nth stairs.
static int stepRequired(int N)
{
    int cnt = 0;
 
    // Till N becomes 0
    while (N > 0)
    {
 
        // Removes the set bits from
        // the right to left
        N = N & (N - 1);
        cnt++;
    }
 
    return cnt;
}
 
// Driver Code
public static void Main(String[] args)
{
 
    // Number of stairs
    int N = 23;
 
    // Function Call
    Console.Write(stepRequired(N));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to count the number of jumps
// required to reach Nth stairs.
function stepRequired(N)
{
    let cnt = 0;
 
    // Till N becomes 0
    while (N)
    {
         
        // Removes the set bits from
        // the right to left
        N = N & (N - 1);
        cnt++;
    }
 
    return cnt;
}
 
// Driver Code
 
// Number of stairs
let N = 23;
 
// Function Call
document.write(stepRequired(N));
 
// This code is contributed by Surbhi Tyagi
 
</script>
Producción: 

4

 

Complejidad temporal: O(log N)
 Espacio auxiliar: O(1)

Segundo Enfoque: Ya que se requiere que los saltos estén en perfecta potencia de 2 . Podemos observar que la función log2 da la potencia perfecta más alta de 2 que se puede lograr menos que N si la encasillamos en un número entero. Entonces podemos restar el pow(2,(int)log2(N)) cada vez de N hasta que su valor sea mayor que 0 mientras incrementamos cnt al mismo tiempo.

C++14

#include <bits/stdc++.h>
 
using namespace std;
 
int stepRequired(int& N)
{
  
    int cnt = 0;
     
    //until N is reached
    while(N>0)
    {
        //subtract highest perfect power of 2 we can reach from previous level
        N-=pow(2,(int)log2(N));
         
        //increment cnt for total number of steps taken
        cnt++;
    }
    return cnt;
}
 
int main()
{
  
    // Number of stairs
    int N = 23;
  
    // Function Call
    cout << stepRequired(N);
    return 0;
}

Java

// Java program for above approach
import java.util.*;
 
class GFG
{
 
static int stepRequired(int N)
{
   
    int cnt = 0;
      
    //until N is reached
    while(N>0)
    {
        //subtract highest perfect power of 2 we can reach from previous level
        N-= Math.pow(2, (int)(Math.log(N) / Math.log(2)));
          
        //increment cnt for total number of steps taken
        cnt++;
    }
    return cnt;
}
 
public static void main(String[] args) {
         
    // Number of stairs
    int N = 23;
   
    // Function Call
    System.out.println(stepRequired(N));
}
}
 
// This code is contributed by sanjoy_62.

Python3

# Python code is contributed by shinjanpatra
import math
 
def stepRequired(N):
  
    cnt = 0
     
    # until N is reached
    while(N > 0):
 
        # subtract highest perfect power of 2 we can reach from previous level
        N -= math.pow(2,math.floor(math.log2(N)))
         
        # increment cnt for total number of steps taken
        cnt += 1
 
    return cnt
 
# driver code
  
# Number of stairs
N = 23
  
# Function Call
print(stepRequired(N))
 
# This code is contributed by shinjanpatra

C#

// C# program for the above approach
using System;
  
class GFG{
  
// Function to count the number of
// jumps required to reach Nth stairs.
static int stepRequired(int N)
{
    int cnt = 0;
  
    //until N is reached
    while (N > 0)
    {
        //subtract highest perfect power of 2 we can reach from previous level
        N-=(int)Math.Pow(2,(int)(Math.Log(N,2)));
  
          
        //increment cnt for total number of steps taken
        cnt++;
    }
  
    return cnt;
}
  
// Driver Code
public static void Main(String[] args)
{
  
    // Number of stairs
    int N = 23;
  
    // Function Call
    Console.Write(stepRequired(N));
}
}
  
// This code is contributed by aditya942003patil

Javascript

<script>
 
// JavaScript code is contributed by shinjanpatra
function stepRequired(N)
{
  
    let cnt = 0;
     
    // until N is reached
    while(N > 0)
    {
        // subtract highest perfect power of 2 we can reach from previous level
        N -= Math.pow(2,Math.floor(Math.log2(N)));
         
        // increment cnt for total number of steps taken
        cnt++;
    }
    return cnt;
}
 
// driver code
  
// Number of stairs
let N = 23;
  
// Function Call
document.write(stepRequired(N));
 
// This code is contributed by shinjanpatra
 
</script>

Complejidad de tiempo: O (log N) 

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por singh3331 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 *