Potencia más cercana a 2 de las frecuencias de cada dígito de un número dado

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:

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *