Forme un número usando rotaciones de bits de N que tengan la misma frecuencia de cada dígito

Posted on by Rudeus Greyrat

Dado un número N , la tarea es convertirlo en un número en el que todos los dígitos distintos tengan la misma frecuencia, rotando sus bits en sentido horario o antihorario. Si no es posible convertir el número imprima -1, de lo contrario imprima el número

Ejemplos: 

Entrada: N = 331
Salida: 421
Explicación: 
Representación binaria de 331: 101001011
Después de una rotación en sentido antihorario – 421: 110100101
421 es un número constante

Entrada: N = 58993
Salida: 51097

 

Planteamiento: La idea es comprobar todos los escenarios posibles, después de rotar los bits del número. Siga los pasos a continuación para resolver este problema:

  1. Use un mapa para realizar un seguimiento de las frecuencias de los dígitos.
  2. Use un conjunto para verificar si todas las frecuencias son iguales o no.
  3. Si el número tiene las mismas frecuencias para todos los dígitos, imprímalo como respuesta
  4. De lo contrario, gire la representación binaria del número y verifique nuevamente.
  5. Si después de todas las rotaciones, no se puede encontrar ningún número que tenga las mismas frecuencias de todos los dígitos, imprima -1.

A continuación se muestra la representación del enfoque anterior.

C++

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to rotate
// the number by one place
int rotate(int N, int bits)
{
 
    // Getting the least significant bit
    int ls = N & 1;
 
    // Rotating the number
    return (N >> 1) | (int(pow(2, (bits - 1))) * ls);
}
 
// Function to check
// if a number is steady or not
bool checkStead(int N)
{
 
    // Map for the frequency of the digits
    map<char, int> mp;
    for (auto i : to_string(N))
        mp[i]++;
 
    // Checking if all the
    // frequencies are same or not
    set<int> se;
    for (auto it = mp.begin(); it != mp.end(); ++it)
        se.insert(it->second);
    if (se.size() == 1)
        return true;
    return false;
}
 
void solve(int N)
{
 
    // Getting the number of bits needed
    int bits = int(log2(N)) + 1;
    bool flag = true;
 
    // Checking all the possible numbers
    for (int i = 1; i < bits; ++i) {
        if (checkStead(N)) {
            cout << N << "\n";
            flag = false;
            break;
        }
        N = rotate(N, bits);
    }
    if (flag)
        cout << -1;
}
 
// Driver Code
int main()
{
 
    int N = 331;
    solve(N);
 
    return 0;
}
 
    // This code is contributed by rakeshsahni

Java

// Java code for the above approach
import java.util.HashMap;
import java.util.HashSet;
 
class GFG
{
   
    // Function to rotate
    // the number by one place
    public static int rotate(int N, int bits) {
 
        // Getting the least significant bit
        int ls = N & 1;
 
        // Rotating the number
        return (N >> 1) | (int) (Math.pow(2, (bits - 1))) * ls;
    }
 
    // Function to check
    // if a number is steady or not
public static boolean checkStead(int N)
{
 
    // Map for the frequency of the digits
    HashMap<String, Integer> mp = new HashMap<String, Integer>();
    for (String i : Integer.toString(N).split("")){
        if(mp.containsKey(i)){
            mp.put(i, mp.get(i) + 1);
        }else{
            mp.put(i, 1);
        }
    }
 
    // Checking if all the
    // frequencies are same or not
    HashSet<Integer> se = new HashSet<Integer>();
    for (String it : mp.keySet())
        se.add(mp.get(it));
    if (se.size() == 1)
        return true;
    return false;
}
 
public static void solve(int N)
{
 
    // Getting the number of bits needed
    int bits = (int)(Math.log(N) / Math.log(2)) + 1;
    boolean flag = true;
 
    // Checking all the possible numbers
    for (int i = 1; i < bits; ++i) {
        if (checkStead(N)) {
            System.out.println(N);
            flag = false;
            break;
        }
        N = rotate(N, bits);
    }
    if (flag)
        System.out.println(-1);
}
 
    // Driver Code
    public static void main(String args[]) {
 
        int N = 331;
        solve(N);
    }
}
 
// This code is contributed by Saurabh Jaiswal

Python3

# Python code for the above approach
import math
 
def solve(N):
 
    # Getting the number of bits needed
    bits = int(math.log(N, 2))+1
    flag = True
 
    # Checking all the possible numbers
    for i in range(1, bits):
        if checkStead(N):
            print(N)
            flag = False
            break
        N = rotate(N, bits)
 
    if flag:
        print(-1)
 
# Function to rotate
# the number by one place
def rotate(N, bits):
   
    # Getting the least significant bit
    ls = N & 1
     
    # Rotating the number
    return (N >> 1) | (2**(bits-1)*ls)
 
# Function to check
# if a number is steady or not
def checkStead(N):
   
    # Map for the frequency of the digits
    mp = {}
    for i in str(N):
        if i in mp:
            mp[i] += 1
        else:
            mp[i] = 1
 
    # Checking if all the
    # frequencies are same or not
    if len(set(mp.values())) == 1:
        return True
    return False
 
 
# Driver Code
N = 331
solve(N)

C#

// C# code for the above approach
using System;
using System.Collections.Generic;
 
class GFG {
 
  // Function to rotate
  // the number by one place
  public static int rotate(int N, int bits)
  {
 
    // Getting the least significant bit
    int ls = N & 1;
 
    // Rotating the number
    return (N >> 1)
      | (int)(Math.Pow(2, (bits - 1))) * ls;
  }
 
  // Function to check
  // if a number is steady or not
  public static bool checkStead(int N)
  {
 
    // Map for the frequency of the digits
    Dictionary<char, int> mp
      = new Dictionary<char, int>();
    foreach(char i in N.ToString())
    {
      if (mp.ContainsKey(i)) {
        mp[i]++;
      }
      else {
        mp[i] = 1;
      }
    }
 
    // Checking if all the
    // frequencies are same or not
    HashSet<int> se = new HashSet<int>();
    foreach(KeyValuePair<char, int> it in mp)
      se.Add(it.Value);
    if (se.Count == 1)
      return true;
    return false;
  }
 
  public static void solve(int N)
  {
 
    // Getting the number of bits needed
    int bits = (int)(Math.Log(N) / Math.Log(2)) + 1;
    bool flag = true;
 
    // Checking all the possible numbers
    for (int i = 1; i < bits; ++i) {
      if (checkStead(N)) {
        Console.WriteLine(N);
        flag = false;
        break;
      }
      N = rotate(N, bits);
    }
    if (flag)
      Console.WriteLine(-1);
  }
 
  // Driver Code
  public static void Main()
  {
 
    int N = 331;
    solve(N);
  }
}
 
// This code is contributed by ukasp.

Javascript

<script>
 
// JavaScript code for the above approach
 
// Function to check if a number
// is steady or not
function checkStead(N)
{
     
    // Map for the frequency of the digits
    let mp = new Map();
    let s = [];
 
    while (N != 0)
    {
        s.push(N % 10);
        N = Math.floor(N / 10)
    }
 
    for(let i = 0; i < s.length; i++)
    {
        if (mp.has(s[i]))
        {
            mp.set(s[i], mp.get(s[i]) + 1)
        }
        else
        {
            mp.set(s[i], 1);
        }
    }
 
    // Checking if all the
    // frequencies are same or not
    let st = new Set([...mp.values()]);
 
    if (st.size == 1)
        return true;
    else
        return false
}
 
// Function to rotate
// the number by one place
function rotate(N, bits)
{
     
    // Getting the least significant bit
    let ls = N & 1;
 
    // Rotating the number
    return ((N >> 1) | (Math.pow(2, bits - 1) * ls))
}
 
function solve(N)
{
     
    // Getting the number of bits needed
    let bits = Math.floor(Math.log2(N)) + 1
    let flag = true
 
    // Checking all the possible numbers
    for(let i = 1; i < bits; i++)
    {
        if (checkStead(N) == 1)
        {
            document.write(N)
            flag = false
            break
        }
        N = rotate(N, bits)
    }
     
    if (flag)
        document.write(-1)
}
 
// Driver Code
N = 331
 
solve(N)
 
// This code is contributed by Potta Lokesh
 
</script>
Producción: 

421

 

Complejidad de tiempo: O(log 2 N)
Espacio auxiliar: O(log 10 N)

Publicación traducida automáticamente

Artículo escrito por rohitkumarsinghcna 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 *