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: 4
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>
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)