Dado un número entero N , la tarea es encontrar el mayor número menor que N que tenga el número máximo de bits establecidos.
Ejemplos:
Entrada: N = 345
Salida: 255
Explicación:
345 en representación binaria es 101011001 con 5 bits establecidos, y 255 es 11111111 con un número máximo de bits establecidos menor que el número entero N.
Entrada: N = 2
Salida: 1
Explicación:
2 en binario La representación es 10 con 1 bit establecido, y 1 tiene un número máximo de bits establecidos menor que el número entero N.
Enfoque ingenuo:
el enfoque ingenuo para resolver el problema es iterar hasta el número entero N – 1 y encontrar la cantidad de bits establecidos para cada número y almacenar el número que tiene los bits establecidos más grandes y los bits establecidos máximos del número.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to Find the
// largest number smaller than integer
// N with maximum number of set bits
#include <bits/stdc++.h>
using namespace std;
// Function to return the largest
// number less than N
int largestNum(int n)
{
int num = 0;
int max_setBits = 0;
// Iterate through all the numbers
for (int i = 0; i < n; i++) {
// Find the number of set bits
// for the current number
int setBits = __builtin_popcount(i);
// Check if this number has the
// highest set bits
if (setBits >= max_setBits) {
num = i;
max_setBits = setBits;
}
}
// Return the result
return num;
}
// Driver code
int main()
{
int N = 345;
cout << largestNum(N);
return 0;
}
Java
// Java implementation to Find the
// largest number smaller than integer
// N with maximum number of set bits
class GFG
{
/* Function to get no of set
bits in binary representation
of positive integer n */
static int countSetBits(int n)
{
int count = 0;
while (n > 0)
{
count += n & 1;
n >>= 1;
}
return count;
}
// Function to return the largest
// number less than N
static int largestNum(int n)
{
int num = 0;
int max_setBits = 0;
// Iterate through all the numbers
for (int i = 0; i < n; i++)
{
// Find the number of set bits
// for the current number
int setBits = countSetBits(i);
// Check if this number has the
// highest set bits
if (setBits >= max_setBits)
{
num = i;
max_setBits = setBits;
}
}
// Return the result
return num;
}
// Driver code
public static void main (String[] args)
{
int N = 345;
System.out.println(largestNum(N));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation to find the
# largest number smaller than integer
# N with maximum number of set bits
# Function to return the largest
# number less than N
def largestNum(n):
num = 0;
max_setBits = 0;
# Iterate through all the numbers
for i in range(n):
# Find the number of set bits
# for the current number
setBits = bin(i).count('1');
# Check if this number has the
# highest set bits
if (setBits >= max_setBits):
num = i;
max_setBits = setBits;
# Return the result
return num;
# Driver code
if __name__ == "__main__" :
N = 345;
print(largestNum(N));
# This code is contributed by AnkitRai01
C#
// C# implementation to Find the
// largest number smaller than integer
// N with a maximum number of set bits
using System;
class GFG{
// Function to get no of set
// bits in binary representation
// of positive integer n
static int countSetBits(int n)
{
int count = 0;
while (n > 0)
{
count += n & 1;
n >>= 1;
}
return count;
}
// Function to return the largest
// number less than N
static int largestNum(int n)
{
int num = 0;
int max_setBits = 0;
// Iterate through all the numbers
for(int i = 0; i < n; i++)
{
// Find the number of set bits
// for the current number
int setBits = countSetBits(i);
// Check if this number has
// the highest set bits
if (setBits >= max_setBits)
{
num = i;
max_setBits = setBits;
}
}
// Return the result
return num;
}
// Driver code
public static void Main(String[] args)
{
int N = 345;
Console.Write(largestNum(N));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript implementation to Find the
// largest number smaller than integer
// N with a maximum number of set bits
// Function to get no of set
// bits in binary representation
// of positive integer n
function countSetBits(n)
{
let count = 0;
while (n > 0)
{
count += n & 1;
n >>= 1;
}
return count;
}
// Function to return the largest
// number less than N
function largestNum(n)
{
let num = 0;
let max_setBits = 0;
// Iterate through all the numbers
for(let i = 0; i < n; i++)
{
// Find the number of set bits
// for the current number
let setBits = countSetBits(i);
// Check if this number has
// the highest set bits
if (setBits >= max_setBits)
{
num = i;
max_setBits = setBits;
}
}
// Return the result
return num;
}
let N = 345;
document.write(largestNum(N));
</script>
Producción
255
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar la solución anterior, debemos observar que el número con los bits más altos seguramente será de la forma 2 k – 1. Los números de la forma 2 k tendrán solo un conjunto de bits, y los números de la forma 2 k – 1 tendrá todos los bits establecidos antes de la k -ésima posición. Entonces, solo necesitamos iterar sobre los valores posibles de k y encontrar el valor más alto justo menos que el número entero N. Dado que estamos iterando sobre la variable exponente, se requerirán como máximo pasos de log(N).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to Find the
// largest number smaller than integer
// N with maximum number of set bits
#include <bits/stdc++.h>
using namespace std;
// Function to return the largest
// number less than N
int largestNum(int n)
{
int num = 0;
// Iterate through all possible values
for (int i = 0; i <= 32; i++)
{
// Multiply the number by 2 i times
int x = (1 << i);
if ((x - 1) <= n)
num = (1 << i) - 1;
else
break;
}
// Return the final result
return num;
}
// Driver code
int main()
{
int N = 345;
cout << largestNum(N);
return 0;
}
Java
// Java implementation to Find the
// largest number smaller than integer
// N with maximum number of set bits
import java.util.*;
class GFG{
// Function to return the largest
// number less than N
static int largestNum(int n)
{
int num = 0;
// Iterate through all possible values
for (int i = 0; i <= 32; i++)
{
// Multiply the number by 2 i times
int x = (1 << i);
if ((x - 1) <= n)
num = (1 << i) - 1;
else
break;
}
// Return the final result
return num;
}
// Driver code
public static void main(String args[])
{
int N = 345;
System.out.print(largestNum(N));
}
}
// This code is contributed by Akanksha_Rai
Python3
# Python3 implementation to find the # largest number smaller than integer # N with the maximum number of set bits # Function to return the largest # number less than N def largestNum(n): num = 0; # Iterate through all possible # values for i in range(32): # Multiply the number by # 2 i times x = (1 << i); if ((x - 1) <= n): num = (1 << i) - 1; else: break; # Return the final result return num; # Driver code if __name__ == "__main__": N = 345; print(largestNum(N)); # This code is contributed by AnkitRai01
C#
// C# implementation to Find the
// largest number smaller than integer
// N with maximum number of set bits
using System;
class GFG{
// Function to return the largest
// number less than N
static int largestNum(int n)
{
int num = 0;
// Iterate through all possible values
for (int i = 0; i <= 32; i++)
{
// Multiply the number by 2 i times
int x = (1 << i);
if ((x - 1) <= n)
num = (1 << i) - 1;
else
break;
}
// Return the final result
return num;
}
// Driver code
public static void Main()
{
int N = 345;
Console.Write(largestNum(N));
}
}
// This code is contributed by Nidhi_Biet
Javascript
<script>
// Javascript implementation to Find the
// largest number smaller than integer
// N with maximum number of set bits
// Function to return the largest
// number less than N
function largestNum(n)
{
let num = 0;
// Iterate through all possible values
for (let i = 0; i <= 32; i++)
{
// Multiply the number by 2 i times
let x = (1 << i);
if ((x - 1) <= n)
num = (1 << i) - 1;
else
break;
}
// Return the final result
return num;
}
let N = 345;
document.write(largestNum(N));
// This code is contributed by suresh07.
</script>
Producción
255
Complejidad de tiempo: O (log N)
Espacio Auxiliar: O(1)