Dado n, encuentre el número más grande que estrictamente no sea mayor que n y cuya representación binaria consista en m unos consecutivos, luego m-1 ceros consecutivos y nada más
Ejemplos:
Input : n = 7 Output : 6 Explanation: 6's binary representation is 110, and 7's is 111, so 6 consists of 2 consecutive 1's and then 1 consecutive 0. Input : 130 Output : 120 Explanation: 28 and 120 are the only numbers <=120, 28 is 11100 consists of 3 consecutive 1's and then 2 consecutive 0's. 120 is 1111000 consists of 4 consecutive 1's and then 3 consecutive 0's. So 120 is the greatest of number<=120 which meets the given condition.
Un enfoque ingenuo será atravesar de 1 a N y verificar cada representación binaria que consta de m 1 consecutivos y m-1 0 consecutivos y almacenar el mayor de ellos que cumpla con la condición dada.
Un enfoque eficiente es observar un patrón de números,
[ 1(1), 6(110), 28(11100), 120(1111000), 496(111110000),….]
Para obtener la fórmula de los números que satisface el condiciones, tomamos 120 como ejemplo
: 120 se representa como 1111000, que tiene m = 4 1 y m = 3 0. Convirtiendo 1111000 a decimal obtenemos:
2^3+2^4+2^5+2^6 que se puede representar como (2^m-1 + 2^m+ 2^m+1 + … 2^m+2, 2^2*m)
2^3*(1+2+2^2+2^3) que se puede representar como (2^(m-1)*(1+2+2^2+2^3+ ..2^(m-1))
2^3*(2^4-1) que se puede representar como [2^(m-1) * (2^m -1)].
Entonces todos los números que cumplen la condición dada se pueden representar como
[2^(m-1) * (2^m-1)]
Podemos iterar hasta que el número no exceda N e imprimir el mayor de todos los elementos posibles. Una observación más cercana mostrará que en m = 33 excederá la marca de 10^18 , por lo que estamos calculando el número en la unidad de tiempo ya que log(32) está cerca de la constante que se requiere para calcular la potencia .
Entonces, la complejidad general será O(1).
C++
// CPP program to find largest number
// smaller than equal to n with m set
// bits then m-1 0 bits.
#include <bits/stdc++.h>
using namespace std;
// Returns largest number with m set
// bits then m-1 0 bits.
long long answer(long long n)
{
// Start with 2 bits.
long m = 2;
// initial answer is 1
// which meets the given condition
long long ans = 1;
long long r = 1;
// check for all numbers
while (r < n) {
// compute the number
r = (int)(pow(2, m) - 1) * (pow(2, m - 1));
// if less than N
if (r < n)
ans = r;
// increment m to get the next number
m++;
}
return ans;
}
// driver code to check the above condition
int main()
{
long long n = 7;
cout << answer(n);
return 0;
}
Java
// java program to find largest number
// smaller than equal to n with m set
// bits then m-1 0 bits.
public class GFG {
// Returns largest number with
// m set bits then m-1 0 bits.
static long answer(long n)
{
// Start with 2 bits.
long m = 2;
// initial answer is 1 which
// meets the given condition
long ans = 1;
long r = 1;
// check for all numbers
while (r < n) {
// compute the number
r = ((long)Math.pow(2, m) - 1) *
((long)Math.pow(2, m - 1));
// if less than N
if (r < n)
ans = r;
// increment m to get
// the next number
m++;
}
return ans;
}
// Driver code
public static void main(String args[]) {
long n = 7;
System.out.println(answer(n));
}
}
// This code is contributed by Sam007
Python3
# Python3 program to find # largest number smaller # than equal to n with m # set bits then m-1 0 bits. import math # Returns largest number # with m set bits then # m-1 0 bits. def answer(n): # Start with 2 bits. m = 2; # initial answer is # 1 which meets the # given condition ans = 1; r = 1; # check for all numbers while r < n: # compute the number r = (int)((pow(2, m) - 1) * (pow(2, m - 1))); # if less than N if r < n: ans = r; # increment m to get # the next number m = m + 1; return ans; # Driver Code print(answer(7)); # This code is contributed by mits.
C#
// C# program to find largest number
// smaller than equal to n with m set
// bits then m-1 0 bits.
using System;
class GFG {
// Returns largest number with
// m set bits then m-1 0 bits.
static long answer(long n)
{
// Start with 2 bits.
long m = 2;
// initial answer is 1 which
// meets the given condition
long ans = 1;
long r = 1;
// check for all numbers
while (r < n) {
// compute the number
r = ((long)Math.Pow(2, m) - 1) *
((long)Math.Pow(2, m - 1));
// if less than N
if (r < n)
ans = r;
// increment m to get
// the next number
m++;
}
return ans;
}
// Driver Code
static public void Main ()
{
long n = 7;
Console.WriteLine(answer(n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find largest number
// smaller than equal to n with m set
// bits then m-1 0 bits.
// Returns largest number with m set
// bits then m-1 0 bits.
function answer( $n)
{
// Start with 2 bits.
$m = 2;
// initial answer is 1
// which meets the
// given condition
$ans = 1;
$r = 1;
// check for all numbers
while ($r < $n)
{
// compute the number
$r = (pow(2, $m) - 1) *
(pow(2, $m - 1));
// if less than N
if ($r < $n)
$ans = $r;
// increment m to get
// the next number
$m++;
}
return $ans;
}
// Driver Code
$n = 7;
echo answer($n);
// This code is contributed by Ajit.
?>
Javascript
<script>
// Javascript program to find largest number
// smaller than equal to n with m set
// bits then m-1 0 bits.
// Returns largest number with
// m set bits then m-1 0 bits.
function answer(n)
{
// Start with 2 bits.
let m = 2;
// initial answer is 1 which
// meets the given condition
let ans = 1;
let r = 1;
// check for all numbers
while (r < n) {
// compute the number
r = (Math.pow(2, m) - 1) *
(Math.pow(2, m - 1));
// if less than N
if (r < n)
ans = r;
// increment m to get
// the next number
m++;
}
return ans;
}
// Driver code
let n = 7;
document.write(answer(n));
</script>
Producción:
6
Complejidad de tiempo: O(1)
Complejidad espacial: O(1)