Dado un entero positivo N , la tarea es imprimir la potencia más cercana de 2 de las frecuencias de cada dígito presente en N . Si existen dos potencias de 2 más cercanas para cualquier frecuencia, imprima la mayor.
Ejemplos:
Entrada: N = 344422
Salida:
2 -> 2
3 -> 1
4 -> 4
Explicación:
La frecuencia del dígito 3 es 1. La potencia más cercana de 2 es 1.
La frecuencia del dígito 4 es 3. La potencia más cercana de 2 es 4 La
frecuencia del dígito 2 es 2. La potencia más cercana de 2 es 2.Entrada: N = 16333331163
Salida:
3 -> 8
1 -> 4
6 -> 2
Enfoque: El problema dado se puede resolver usando Hashing . Siga los pasos a continuación para resolver el problema dado:
- Inicialice una string , diga S y convierta el entero N dado y guárdelo en la string S.
- Atraviese la string S y almacene la frecuencia de cada carácter en un mapa , digamos M.
- Ahora, recorra el Mapa M e imprima la potencia de 2 más cercana de la frecuencia de cada dígito almacenado en el Mapa .
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 nearest power of
// 2 for all frequencies in the Map freq
void nearestPowerOfTwoUtil(
unordered_map<char, int>& freq)
{
// Traverse the Map
for (auto& it : freq) {
cout << it.first << " -> ";
// Calculate log of the
// current array element
int lg = log2(it.second);
int a = pow(2, lg);
int b = pow(2, lg + 1);
// Find the nearest power of 2
// for the current frequency
if ((it.second - a)
< (b - it.second)) {
cout << a << endl;
}
else {
cout << b << endl;
}
}
}
// Function to find nearest power of 2
// for frequency of each digit of num
void nearestPowerOfTwo(string& S)
{
// Length of string
int N = S.size();
// Stores the frequency of each
// character in the string
unordered_map<char, int> freq;
// Traverse the string S
for (int i = 0; i < N; i++) {
freq[S[i]]++;
}
// Function call to generate
// nearest power of 2 for each
// frequency
nearestPowerOfTwoUtil(freq);
}
// Driver Code
int main()
{
string N = "16333331163";
nearestPowerOfTwo(N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to find the nearest power of
// 2 for all frequencies in the Map freq
static void nearestPowerOfTwoUtil(HashMap<Character, Integer> freq)
{
// Traverse the Map
for (char key : freq.keySet())
{
System.out.print(key + " -> ");
// Calculate log of the
// current array element
int lg = (int)(Math.log(freq.get(key) / Math.log(2)));
int a = (int)Math.pow(2, lg);
int b = (int)Math.pow(2, lg + 1);
// Find the nearest power of 2
// for the current frequency
if ((freq.get(key) - a) < (b - freq.get(key))) {
System.out.println(a);
}
else {
System.out.println(b);
}
}
}
// Function to find nearest power of 2
// for frequency of each digit of num
static void nearestPowerOfTwo(String S)
{
// Length of string
int N = S.length();
// Stores the frequency of each
// character in the string
HashMap<Character, Integer> freq = new HashMap<>();
// Traverse the string S
for (int i = 0; i < N; i++)
{
freq.put(S.charAt(i), freq.getOrDefault(S.charAt(i), 0) + 1);
}
// Function call to generate
// nearest power of 2 for each
// frequency
nearestPowerOfTwoUtil(freq);
}
// Driver Code
public static void main(String[] args)
{
String N = "16333331163";
nearestPowerOfTwo(N);
}
}
// This code is contributed by Kingash.
Python3
# Python3 program for the above approach
from math import log2, pow
# Function to find the nearest power of
# 2 for all frequencies in the Map freq
def nearestPowerOfTwoUtil(freq):
# Traverse the Map
temp = {}
for key,value in freq.items():
# Calculate log of the
# current array element
lg = int(log2(value))
a = int(pow(2, lg))
b = int(pow(2, lg + 1))
# Find the nearest power of 2
# for the current frequency
if ((value - a) < (b - value)):
temp[(int(a))] = key
else:
temp[(int(b))] = key
for key,value in temp.items():
print(value,"->",key)
# Function to find nearest power of 2
# for frequency of each digit of num
def nearestPowerOfTwo(S):
# Length of string
N = len(S)
# Stores the frequency of each
# character in the string
freq = {}
# Traverse the string S
for i in range(N):
if(S[i] in freq):
freq[S[i]] += 1
else:
freq[S[i]] = 1
# Function call to generate
# nearest power of 2 for each
# frequency
nearestPowerOfTwoUtil(freq)
# Driver Code
if __name__ == '__main__':
N = "16333331163"
nearestPowerOfTwo(N)
# This code is contributed by bgangwar59.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the nearest power of
// 2 for all frequencies in the Map freq
static void nearestPowerOfTwoUtil(
Dictionary<char, int> freq)
{
// Traverse the Map
foreach (KeyValuePair<char, int> entry in freq)
{
char key = entry.Key;
Console.Write(key + " -> ");
// Calculate log of the
// current array element
int lg = (int)(Math.Log(freq[key] /
Math.Log(2)));
int a = (int)Math.Pow(2, lg);
int b = (int)Math.Pow(2, lg + 1);
// Find the nearest power of 2
// for the current frequency
if ((freq[key] - a) < (b - freq[key]))
{
Console.Write(a + "\n");
}
else
{
Console.Write(b + "\n");
}
}
}
// Function to find nearest power of 2
// for frequency of each digit of num
static void nearestPowerOfTwo(string S)
{
// Length of string
int N = S.Length;
// Stores the frequency of each
// character in the string
Dictionary<char,
int> freq = new Dictionary<char,
int>();
// Traverse the string S
for(int i = 0; i < N; i++)
{
if (freq.ContainsKey(S[i]))
freq[S[i]] += 1;
else
freq[S[i]] = 1;
}
// Function call to generate
// nearest power of 2 for each
// frequency
nearestPowerOfTwoUtil(freq);
}
// Driver Code
public static void Main()
{
string N = "16333331163";
nearestPowerOfTwo(N);
}
}
// This code is contributed by ipg2016107
Javascript
<script>
// Javascript program for the above approach
// Function to find the nearest power of
// 2 for all frequencies in the Map freq
function nearestPowerOfTwoUtil(freq)
{
// Traverse the Map
freq.forEach((value, key) => {
document.write( key + " -> ");
// Calculate log of the
// current array element
var lg = parseInt(Math.log2(value));
var a = Math.pow(2, lg);
var b = Math.pow(2, lg + 1);
// Find the nearest power of 2
// for the current frequency
if ((value - a)
< (b - value)) {
document.write( a + "<br>");
}
else {
document.write( b + "<br>");
}
});
}
// Function to find nearest power of 2
// for frequency of each digit of num
function nearestPowerOfTwo(S)
{
// Length of string
var N = S.length;
// Stores the frequency of each
// character in the string
var freq = new Map();
// Traverse the string S
for (var i = 0; i < N; i++) {
if(freq.has(S[i]))
{
freq.set(S[i], freq.get(S[i])+1)
}
else
{
freq.set(S[i], 1)
}
}
// Function call to generate
// nearest power of 2 for each
// frequency
nearestPowerOfTwoUtil(freq);
}
// Driver Code
var N = "16333331163";
nearestPowerOfTwo(N);
</script>
Producción:
3 -> 8 1 -> 4 6 -> 2
Complejidad de tiempo: O(log 10 N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por subhammahato348 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA