Given a number N, the task is to convert it into a number in which all distinct digits have the same frequency, by rotating its bits either clockwise or anti-clockwise. If it is not possible to convert the number print -1, otherwise print the number
Examples:
Input: N = 331
Output: 421
Explanation:
Binary representation of 331: 101001011
After an anti-clockwise rotation – 421: 110100101
421 is a steady numberInput: N = 58993
Output: 51097
Approach: The idea is to check all the possible scenarios, after rotating the bits of the number. Follow the below steps to solve this problem:
- Use a map to keep track of the frequencies of the digits.
- Use a set to check if all the frequencies are the same or not.
- If the number has the same frequencies for all digits, then print it as the answer
- Else rotate the binary representation of the number and check again.
- If after all the rotations, no number can be found having the same frequencies of all digits, then print -1.
Below is the representation of the above approach.
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to rotate// the number by one placeint 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 notbool 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 Codeint main(){ int N = 331; solve(N); return 0;} // This code is contributed by rakeshsahni |
Java
// Java code for the above approachimport 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 notpublic 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 approachimport mathdef 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 placedef 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 notdef 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 CodeN = 331solve(N) |
C#
// C# code for the above approachusing 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 notfunction 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 placefunction 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 CodeN = 331solve(N)// This code is contributed by Potta Lokesh</script> |
Output:
421
Time Complexity: O(log2N)
Auxiliary Space: O(log10N)
