Approach
The idea to solve this problem is quite simple, but you should remember it for future questions.
Hereafter every rotation, we have to check if our conditions are satisfied.
Can you guess how we can store the frequency for every digit in an efficient manner?
- We can use Hashmap data structure to track the frequencies of every digit.
- And HashSet data structure will check whether all the digits have the same frequency or not.
- If the number contains digits with the same frequency, print it as the answer.
- If not, then rotate the number using the stated formula:
(n >> 1) | (int) (Math.pow(2, (bits - 1))) * lsb
Where lsb = n&1
- If, after the rotations, no number can be found having the same frequency of all the digits, then print -1.
Also see, Euclid GCD Algorithm
Implementation
import java.util.HashMap;
import java.util.HashSet;
class Solution
{
// To perform the rotation operation
public static int rotation(int n, int bit) {
// Getting the LSB
int lsb = n & 1;
// Rotating the number by '1'
return (n >> 1) | (int) (Math.pow(2, (bit - 1))) * lsb;
}
// Function to check
// if a number is steady or not
public static boolean frequency(int N){
// To store the frequency of every bit
HashMap<String, Integer> map = new HashMap<String, Integer>();
for (String i : Integer.toString(N).split("")){
if(map.containsKey(i)){
map.put(i, map.get(i) + 1);
}
else{
map.put(i, 1);
}
}
// To check that frequency of every digit is same or not
HashSet<Integer> hs = new HashSet<Integer>();
for (String it : map.keySet())
hs.add(map.get(it));
if (hs.size() == 1)
return true;
return false;
}
public static void solve(int n){
int bit = (int)(Math.log(n) / Math.log(2)) + 1;
boolean f = true;
// To check for all possible solutions
for (int i = 1; i < bit; ++i) {
if (frequency(n)) {
System.out.println(n);
f = false;
break;
}
n = rotation(n, bit);
}
if (f)
System.out.println(-1);
}
// Main function
public static void main(String args[]) {
int n = 331;
solve(n);
}
}
You can also try this code with Online Java Compiler
Output
421
You can also try this code with Online Java Compiler
Complexity Analysis
Time Complexity:
The time complexity to find a number having the same frequency for every digit is O(logn).
Space Complexity:
The space complexity to find a number having the same frequency for every digit after performing the rotations is O(logn).
Frequently Asked Questions
-
What do you mean by HashMap data structure?
HashMap is a data structure that stores the data in (Key, Value) pairs, and you can access them by an index of another type (e.g., an Integer).
-
What will be the time complexity to find a number using bit rotations having the same frequency?
The time complexity to solve this problem is O(logN).
-
How is HashMap different from HashSet?
HashSet implements Set interface and objects are stored while HashMap implements Map interface which maps a key to value.
Key Takeaways
In this blog, we have covered the following things:
- What the problem is, along with the example.
- Approach to ponder upon.
- Implementation in the Java language.
Before stepping into this problem, you can try problems similar to this concept like
Binary Flip and many more. Binary shifting is an important topic to cover in Bit Manipulation for breaking complex problems into our desired output.
Coding Ninjas Studio is a one-stop destination for various DSA questions typically asked in interviews to practice more such problems.
Keep Learning, Keep Growing!!!
134+ registered 
