Dado un rango de números [L, R] , la tarea es encontrar todos los números X en el rango dado, de modo que X = suma de dígitos elevados al recuento de bits establecidos de X , es decir, si hay N bits establecidos en representación binaria de X y X = X 1 X 2 X 3 … entonces X = (X 1 ) N + (X 2 ) N + (X 3 ) N + . . .
Ejemplos:
Entrada: L = 0, R = 10000
Salida: 1, 2, 4, 8, 4150, 9474
Explicación: Para 2 (binario = 10): número de bits definidos = 1 y 2 = 2^1.
Así que este es un número requerido. Lo mismo para los otros números también.Entrada: L = 10000, R = 1000000
Salida: -1
Explicación: No hay tales números en el rango dado.
Enfoque: el problema dado se puede resolver verificando todos los números en el rango [L, R] y si cumplen la condición o no. Se puede hacer con la ayuda del Algoritmo de Brian Kernighan .
Siga los pasos que se mencionan a continuación para resolver el problema.
- Ejecute un ciclo de L a R y en cada iteración verifique que el número sea un número de índice o no.
- Primero calcule el número de bits establecidos en el número decimal a partir de su representación binaria.
- Luego, Inicializar original = N , Res = 0 , Índice = Recuento de bits establecidos .
- Ejecutar un ciclo mientras N > 0
- Encuentre el último dígito del número, digamos ( L ),
- Añadir Índice L a Res.
- Elimina el último dígito del número.
- Si Original = Res , este será uno de los números requeridos.
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;
#define ll long long
// Function to return Number of
// set bits in any decimal number
int countSetBits(ll N)
{
int Count = 0;
while (N) {
N = N & (N - 1);
Count++;
}
return Count;
}
// Function to check whether the
// number is index number or not
bool check(int Index, ll N)
{
ll Original = N, Res = 0;
if(N == 0)
return false;
while (N != 0) {
int L = N % 10;
Res += pow(L, Index);
N = N / 10;
}
return Original == Res;
}
// Function to find the numbers
vector<int> findNum(int l, int r)
{
// Vector to store the numbers
vector<int> ans;
for (ll i = l; i <= r; i++) {
int BitCount = countSetBits(i);
if (check(BitCount, i))
ans.push_back(i);
}
return ans;
}
// Driver Code
int main()
{
int L = 0, R = 10000;
// Function call
vector<int> res = findNum(L, R);
if(res.size()==0)
cout << -1 << endl;
for (int x : res)
cout << x << " ";
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to return Number of
// set bits in any decimal number
static int countSetBits(long N)
{
int Count = 0;
while (N != 0) {
N = N & (N - 1);
Count++;
}
return Count;
}
// Function to check whether the
// number is index number or not
static boolean check(int Index, long N)
{
long Original = N, Res = 0;
if(N == 0)
return false;
while (N != 0) {
long L = N % 10;
Res += Math.pow(L, Index);
N = N / 10;
}
return Original == Res;
}
// Function to find the numbers
static Vector<Integer> findNum(int l, int r)
{
// Vector to store the numbers
Vector<Integer> ans = new Vector<Integer>();
for (int i = l; i <= r; i++) {
int BitCount = countSetBits(i);
if (check(BitCount, i))
ans.add(i);
}
return ans;
}
// Driver Code
public static void main (String[] args) {
int L = 0, R = 10000;
// Function call
Vector<Integer> res = findNum(L, R);
if(res.size()==0)
System.out.println(-1);
res.forEach((x) -> System.out.print(x + " "));
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python code to implement the above approach # Function to return Number of # set bits in any decimal number def countSetBits(N): Count = 0 while (N): N = N & (N - 1) Count += 1 return Count # Function to check whether the # number is index number or not def check(Index, N): Original,Res = N,0 if(N == 0): return False while (N != 0): L = N % 10 Res += pow(L, Index) N = N // 10 return Original == Res # Function to find the numbers def findNum(l, r): # Vector to store the numbers ans = [] for i in range(l,r + 1): BitCount = countSetBits(i) if (check(BitCount, i)): ans.append(i) return ans # Driver Code L,R = 0,10000 # Function call res = findNum(L, R) if(len(res)==0): print(-1) for x in res: print(x , end = " ") # This code is contributed by shinjanpatra
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to return Number of
// set bits in any decimal number
public static int countSetBits(long N)
{
int Count = 0;
while (N != 0) {
N = N & (N - 1);
Count++;
}
return Count;
}
// Function to check whether the
// number is index number or not
public static bool check(int Index, long N)
{
long Original = N, Res = 0;
if(N == 0)
return false;
while (N != 0) {
long L = N % 10;
Res += (long)Math.Pow(L, Index);
N = N / 10;
}
return Original == Res;
}
// Function to find the numbers
public static List<int> findNum(int l, int r)
{
// Vector to store the numbers
List<int> ans = new List<int>();
for (int i = l; i <= r; i++) {
int BitCount = countSetBits(i);
if (check(BitCount, i))
ans.Add(i);
}
return ans;
}
// Driver Code
public static void Main (String[] args) {
int L = 0, R = 10000;
// Function call
List<int> res = findNum(L, R);
if(res.Count == 0)
Console.WriteLine(-1);
for (int i = 0; i < res.Count; i++)
Console.Write(res[i] + " ");
}
}
// This code is contributed by phasing17
Javascript
<script>
// JavaScript program for the above approach
// Function to return Number of
// set bits in any decimal number
const countSetBits = (N) => {
let Count = 0;
while (N) {
N = N & (N - 1);
Count++;
}
return Count;
}
// Function to check whether the
// number is index number or not
const check = (Index, N) => {
let Original = N, Res = 0;
while (N != 0) {
let L = N % 10;
Res += Math.pow(L, Index);
N = parseInt(N / 10);
}
return Original == Res;
}
// Function to find the numbers
const findNum = (l, r) => {
// Vector to store the numbers
let ans = [];
for (let i = l; i <= r; i++) {
let BitCount = countSetBits(i);
if (check(BitCount, i))
ans.push(i);
}
return ans;
}
// Driver Code
let L = 0, R = 10000;
// Function call
let res = findNum(L, R);
for (let x in res)
document.write(`${res[x]} `);
// This code is contributed by rakeshsahni
</script>
Producción
1 2 4 8 4150 9474
Complejidad de tiempo : O(R * d) donde d es el número máximo de bits en un número
Espacio auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA