Dado un entero positivo N , la tarea es encontrar el número mínimo de restas de potencia de 2 requeridas para convertir N en 0.
Ejemplos:
Entrada: 10
Salida: 2
Explicación: Cuando restamos 8 de 10 (10 – (2^3) = 2), entonces quedará 2.
Después de eso, reste 2 de 2 ^ 0, es decir, 2 – 2 ^ 0 = 0.
Por lo tanto, estamos haciendo dos operaciones para hacer que N = 0.Entrada: 5
Salida: 2
Planteamiento: El planteamiento del problema se basa en la siguiente idea:
Como necesitamos minimizar el número de sustracciones, entonces reste la potencia de 2 tan grande como sea posible. Este será el mismo que el número de bits establecidos en la representación binaria de N.
Siga la siguiente ilustración para una mejor comprensión.
Ilustración:
Tomar N = 10
1er paso: El valor máximo que se puede restar es 8
Entonces N = 10 – 8 = 2.2do paso: El valor máximo que se puede restar es 2
Entonces N = 2 – 2 = 0.Ahora vea la representación binaria de 10 = «1010».
Tiene 2 bits establecidos. Así que los pasos mínimos requeridos = 2
Siga el siguiente paso para implementar el enfoque:
- Iterar de i = 1 a 63 :
- Compruebe si ese bit de la representación binaria de N está establecido.
- Si está establecido, incrementa el conteo de bits establecidos.
- Devuelve el recuento final de bits establecidos.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the number of
// operation to make the N zero
int find_no_of_set_bits(long long n)
{
// Take variable to count the number
// of operation
int set_bit_count = 0;
for (int i = 0; i < 63; i++) {
if (n & (1LL << i)) {
set_bit_count++;
}
}
return set_bit_count;
}
// Driver code
int main()
{
long long N = 10;
// Function call
cout << find_no_of_set_bits(N) << endl;
return 0;
}
Java
// Java code to implement the approach
import java.io.*;
class GFG
{
// Function to find the number of
// operation to make the N zero
public static int find_no_of_set_bits(long n)
{
// Take variable to count the number
// of operation
int set_bit_count = 0;
for (int i = 0; i < 63; i++) {
if ((n & ((long)1 << i)) != 0) {
set_bit_count++;
}
}
return set_bit_count;
}
// Driver code
public static void main(String[] args)
{
long N = 10;
// Function call
System.out.println(find_no_of_set_bits(N));
}
}
// This code is contributed by Rohit Pradhan
Python3
# Python code to implement the approach # Function to find the number of # operation to make the N zero def find_no_of_set_bits(n): # Take variable to count the number # of operation set_bit_count = 0 for i in range(63): if (n & (1<< i)): set_bit_count += 1 return set_bit_count # Driver code N = 10 # Function call print(find_no_of_set_bits(N)) # This code is contributed by shinjanpatra
C#
// C# code to implement the approach
using System;
public class GFG
{
// Function to find the number of
// operation to make the N zero
public static int find_no_of_set_bits(long n)
{
// Take variable to count the number
// of operation
int set_bit_count = 0;
for (int i = 0; i < 63; i++) {
if ((n & ((long)1 << i)) != 0) {
set_bit_count++;
}
}
return set_bit_count;
}
// Driver Code
public static void Main(string[] args)
{
long N = 10;
// Function call
Console.WriteLine(find_no_of_set_bits(N));
}
}
// This code is contributed by phasing17
Javascript
<script>
// JavaScript code to implement the approach
// Function to find the number of
// operation to make the N zero
function find_no_of_set_bits(n)
{
// Take variable to count the number
// of operation
var set_bit_count = 0;
for (var i = 0; i < 32; i++) {
if ((n & (1 << i)) != 0) {
set_bit_count++;
}
}
return set_bit_count;
}
// Driver code
var N = 10;
// Function call
document.write(find_no_of_set_bits(N));
// This code is contributed by phasing17
</script>
Producción
2
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Otro enfoque
Convierta el número a su formato de string binaria usando funciones integradas, luego cuente los números de «1» presentes en la string binaria usando también funciones integradas.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
int find_no_of_set_bits(int n)
{
int no_of_set_bits = 0;
for (int i = 1; i <= n; i++) {
string str = to_string(i);
no_of_set_bits += count(str.begin(), str.end(), '1');
}
return no_of_set_bits;
}
// driver function
int main()
{
int N = 10;
// Function call
cout << find_no_of_set_bits(N);
return 0;
}
// This code is contributed by sanjoy_62.
Java
// Java code to implement the approach
import java.io.*;
class GFG
{
// Function to find the number of
// operation to make the N zero
public static int find_no_of_set_bits(int n)
{
int no_of_set_bits = 0;
for (int i = 1; i <= n; i++)
{
// Converting the number to binary string
String bin_N = String.valueOf(i);
// counting the number of "1"s in bin_N
no_of_set_bits += bin_N.split("1", -1) . length - 1;
}
return no_of_set_bits;
}
public static void main(String[] args)
{
int N = 10;
// Function call
System.out.println(find_no_of_set_bits(N));
}
}
// This code is contributed by code_hunt.
Python3
# Python code to implement the approach
# Function to find the number of
# operation to make the N zero
def find_no_of_set_bits(n):
# Converting the number to binary string
bin_N = bin(N)
# counting the number of "1"s in bin_N
no_of_set_bits = bin_N.count("1")
return no_of_set_bits
# Driver code
N = 10
# Function call
print(find_no_of_set_bits(N))
# This code is contributed by phasing17
C#
// C# program for the above approach
using System;
class GFG{
static int find_no_of_set_bits(int n)
{
int no_of_set_bits = 0;
for (int i = 1; i <= n; i++)
{
string bin_N = i.ToString();
no_of_set_bits += bin_N .Split('1') . Length - 1;
}
return no_of_set_bits ;
}
// Driver Code
public static void Main(String[] args)
{
// Given number N
int N = 10;
// Function call
Console.Write(find_no_of_set_bits(N));
}
}
// This code is contributed by avijitmondal1998.
Javascript
<script>
// JS code to implement the approach
// Function to find the number of
// operation to make the N zero
function find_no_of_set_bits(n)
{
// Converting the number to binary string
var bin_N = N.toString(2);
// counting the number of "1"s in bin_N
var no_of_set_bits = (bin_N.match(/1/g) || []).length;
return no_of_set_bits;
}
// Driver code
var N = 10;
// Function call
document.write(find_no_of_set_bits(N))//
// This code is contributed by phasing17
</script>
Producción
2
Complejidad temporal: O(1)
Espacio auxiliar : O(1)
Otro enfoque
El número de bits establecidos en un número se puede contar en tiempo O(1) usando una tabla de búsqueda. La implementación de la tabla de búsqueda se muestra a continuación:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// defining the limit
// which is 64 bytes
const int LIMIT = 64;
int lookUpTable[LIMIT];
// Function to build
// the lookup table
void createLookUpTable()
{
// To initially generate the
// table algorithmically
lookUpTable[0] = 0;
for (int i = 0; i < LIMIT; i++) {
lookUpTable[i] = (i & 1) + lookUpTable[i / 2];
}
}
// Function to count the number
// of set bits using a lookup table
int countSetBits(int n)
{
return (lookUpTable[n & 0xff]
+ lookUpTable[(n >> 8) & 0xff]
+ lookUpTable[(n >> 16) & 0xff]
+ lookUpTable[n >> 24]);
}
// Driver code
int main()
{
// building the lookup table
createLookUpTable();
int n = 10;
cout << countSetBits(n);
}
// this code is contributed by phasing17
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
static final int LIMIT = 64;
static int[] lookUpTable = new int[LIMIT];
// Function to build
// the lookup table
public static void createLookUpTable()
{
// To initially generate the
// table algorithmically
lookUpTable[0] = 0;
for (int i = 0; i < LIMIT; i++) {
lookUpTable[i] = (i & 1) + lookUpTable[i / 2];
}
}
// Function to count the number
// of set bits using a lookup table
public static int countSetBits(int n)
{
return (lookUpTable[n & 0xff]
+ lookUpTable[(n >> 8) & 0xff]
+ lookUpTable[(n >> 16) & 0xff]
+ lookUpTable[n >> 24]);
}
public static void main(String[] args)
{
createLookUpTable();
int n = 10;
System.out.println(countSetBits(n));
}
}
// This code is contributed by KaaL-EL.
Python3
# Python3 program to implement the approach LIMIT = 64 lookUpTable = [None for _ in range(LIMIT)] # Function to build # the lookup table def createLookUpTable(): # To initially generate the # table algorithmically lookUpTable[0] = 0 for i in range(LIMIT): lookUpTable[i] = (i & 1) + lookUpTable[(i // 2)] # Function to count the number # of set bits using a lookup table def countSetBits(n): return (lookUpTable[n & 0xff] + lookUpTable[(n >> 8) & 0xff] + lookUpTable[(n >> 16) & 0xff] + lookUpTable[n >> 24]) # Driver Code createLookUpTable() n = 10 print(countSetBits(n)) # This code is contributed by phasing17
C#
// C# program to implement the approach
using System;
class GFG {
static int LIMIT = 64;
static int[] lookUpTable = new int[LIMIT];
// Function to build
// the lookup table
public static void createLookUpTable()
{
// To initially generate the
// table algorithmically
lookUpTable[0] = 0;
for (int i = 0; i < LIMIT; i++) {
lookUpTable[i] = (i & 1) + lookUpTable[i / 2];
}
}
// Function to count the number
// of set bits using a lookup table
public static int countSetBits(int n)
{
return (lookUpTable[n & 0xff]
+ lookUpTable[(n >> 8) & 0xff]
+ lookUpTable[(n >> 16) & 0xff]
+ lookUpTable[n >> 24]);
}
// Driver Code
public static void Main(string[] args)
{
createLookUpTable();
int n = 10;
// Function call
Console.WriteLine(countSetBits(n));
}
}
// This code is contributed by phasing17
Javascript
// JavaScript program to implement the approach
let LIMIT = 64;
let lookUpTable = new Array(LIMIT);
// Function to build
// the lookup table
function createLookUpTable()
{
// To initially generate the
// table algorithmically
lookUpTable[0] = 0;
for (let i = 0; i < LIMIT; i++) {
lookUpTable[i]
= (i & 1) + lookUpTable[Math.floor(i / 2)];
}
}
// Function to count the number
// of set bits using a lookup table
function countSetBits(n)
{
return (lookUpTable[n & 0xff]
+ lookUpTable[(n >> 8) & 0xff]
+ lookUpTable[(n >> 16) & 0xff]
+ lookUpTable[n >> 24]);
}
//Driver Code
createLookUpTable();
let n = 10;
console.log(countSetBits(n));
// This code is contributed by phasing17
Producción
2
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por abhilashreddy1676 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA