Dado un número entero N, la tarea es encontrar la frecuencia máxima de bits establecidos entre todos los pares de números enteros de 0 a N que produzcan una suma como N.
Ejemplos:
Entrada: N = 5
Salida: 3
Explicación:
Todos los pares son {0, 5}, {1, 4}, {2, 3} que tiene una suma de 5.
0 (0000) y 5 (0101), número de conjunto de bits = 2
1 (0001) y 4 (0100), número de conjunto de bits = 2
2 (0010) y 3 (0011), número de conjunto de bits = 3, por lo tanto, 3 es el máximo.Entrada: N = 11
Salida: 4
Explicación:
Todos los pares son {0, 11}, {1, 10}, {2, 9}, {3, 8}, {4, 7}, {5, 6} y la respuesta máxima será para el par {4, 7}
4 = 1000 y 7 = 0111, número total de bits establecidos = 1 + 3 = 4
Enfoque ingenuo: la forma más sencilla de resolver este problema es generar todos los pares posibles con suma N y calcular la suma máxima de los bits establecidos de todos esos pares, e imprimir el número máximo de suma de bits establecidos.
Complejidad de tiempo : O(N * log N)
Espacio auxiliar : O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar a través de estos pasos:
- Encuentre un número menor que igual a N cuyos bits, desde el bit menos significativo hasta el bit más significativo, sean bits establecidos. Ese número será el primer número del par.
- Calcule el número de bits establecidos en el par {primero, N-primero} y súmelo.
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 the first number
int create_first_no(int n)
{
// Length of the binary from
int length = 0;
// Number of set bits
int freq_set_bits = 0;
int ans = 0;
while (n) {
// Update the first number
ans = ans << 1;
ans = ans + 1;
// Increment length
length++;
// Update the frequency
if ((n & 1))
freq_set_bits += 1;
n = n >> 1;
}
// Check if n does not have all the
// bits as set bits then make
// the first as less than n
if (length != freq_set_bits)
ans = (ans >> 1);
// Return the first value
return ans;
}
// Function to calculate maximum
// set bit frequency sum
int maxSetBits(int n)
{
// First value of pair
int first = create_first_no(n);
// Second value of pair
int second = n - first;
// __builtin_popcount() is inbuilt
// function to count the number of set bits
int freq_first
= __builtin_popcount(first);
int freq_second
= __builtin_popcount(second);
// Return the sum of freq of setbits
return freq_first + freq_second;
}
// Driver Code
int main()
{
int N = 5;
// Function call
cout << maxSetBits(N);
return 0;
}
Java
// Java program to implement the
// above approach
import java.util.*;
class GFG {
// Function to find the first number
static int create_first_no(int n)
{
// Length of the binary from
int length = 0;
// Number of set bits
int freq_set_bits = 0;
int ans = 0;
while (n != 0)
{
// Update the first number
ans = ans << 1;
ans = ans + 1;
// Increment length
length++;
// Update the frequency
if ((n & 1) == 1)
freq_set_bits += 1;
n = n >> 1;
}
// Check if n does not have all the
// bits as set bits then make
// the first as less than n
if (length != freq_set_bits)
ans = (ans >> 1);
// Return the first value
return ans;
}
// Function to calculate maximum
// set bit frequency sum
static int maxSetBits(int n)
{
// First value of pair
int first = create_first_no(n);
// Second value of pair
int second = n - first;
// Integer.bitCount() is inbuilt
// function to count the number of set bits
int freq_first = Integer.bitCount(first);
int freq_second = Integer.bitCount(second);
// Return the sum of freq of setbits
return freq_first + freq_second;
}
// Driver code
public static void main(String[] args)
{
int N = 5;
// Function call
System.out.println(maxSetBits(N));
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the
# above approach
# Function to find the
# first number
def create_first_no(n):
# Length of the binary
# from
length = 0
# Number of set bits
freq_set_bits = 0
ans = 0
while (n != 0):
# Update the first number
ans = ans << 1
ans = ans + 1
# Increment length
length += 1
# Update the frequency
if ((n & 1) != 0):
freq_set_bits += 1
n = n >> 1
# Check if n does not have
# all the bits as set bits
# then make the first as
# less than n
if (length != freq_set_bits):
ans = (ans >> 1)
# Return the first value
return ans
# Function to calculate maximum
# set bit frequency sum
def maxSetBits(n):
# First value of pair
first = create_first_no(n)
# Second value of pair
second = n - first
# __builtin_popcount() is
# inbuilt function to count
# the number of set bits
freq_first = bin(first).count('1')
freq_second = bin(second).count('1')
# Return the sum of
# freq of setbits
return (freq_first +
freq_second)
# Driver code
N = 5
# Function call
print(maxSetBits(N))
# This code is contributed by divyeshrabadiya07
C#
// C# program to implement the
// above approach
using System;
using System.Linq;
class GFG {
// Function to find the first number
static int create_first_no(int n)
{
// Length of the binary from
int length = 0;
// Number of set bits
int freq_set_bits = 0;
int ans = 0;
while (n != 0)
{
// Update the first number
ans = ans << 1;
ans = ans + 1;
// Increment length
length++;
// Update the frequency
if ((n & 1) == 1)
freq_set_bits += 1;
n = n >> 1;
}
// Check if n does not have all the
// bits as set bits then make
// the first as less than n
if (length != freq_set_bits)
ans = (ans >> 1);
// Return the first value
return ans;
}
public static int countSetBits(int n)
{
// base case
if (n == 0)
return 0;
else
// if last bit set
// add 1 else add 0
return (n & 1) + countSetBits(n >> 1);
}
// Function to calculate maximum
// set bit frequency sum
static int maxSetBits(int n)
{
// First value of pair
int first = create_first_no(n);
// Second value of pair
int second = n - first;
//countSetBits function to
//count the number of set bits
int freq_first = countSetBits(first);
int freq_second = countSetBits(second);
// Return the sum of freq of setbits
return freq_first + freq_second;
}
// Driver code
public static void Main(string[] args)
{
int N = 5;
// Function call
Console.Write(maxSetBits(N));
}
}
// This code is contributed by Ritik Bansal
Javascript
<script>
// Javascript program for
// the above approach
// Function to find the first number
function create_first_no(n)
{
// Length of the binary from
let length = 0;
// Number of set bits
let freq_set_bits = 0;
let ans = 0;
while (n != 0)
{
// Update the first number
ans = ans << 1;
ans = ans + 1;
// Increment length
length++;
// Update the frequency
if ((n & 1) == 1)
freq_set_bits += 1;
n = n >> 1;
}
// Check if n does not have all the
// bits as set bits then make
// the first as less than n
if (length != freq_set_bits)
ans = (ans >> 1);
// Return the first value
return ans;
}
function countSetBits(n)
{
// base case
if (n == 0)
return 0;
else
// if last bit set
// add 1 else add 0
return (n & 1) + countSetBits(n >> 1);
}
// Function to calculate maximum
// set bit frequency sum
function maxSetBits(n)
{
// First value of pair
let first = create_first_no(n);
// Second value of pair
let second = n - first;
//countSetBits function to
//count the number of set bits
let freq_first = countSetBits(first);
let freq_second = countSetBits(second);
// Return the sum of freq of setbits
return freq_first + freq_second;
}
// Driver Code
let N = 5;
// Function call
document.write(maxSetBits(N));
</script>
Producción:
3
Complejidad temporal: O(logN)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por swapnoneelmajumdar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA