Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem statement
2.1.
Example 1:
3.
Approach
4.
Implementation
5.
Complexity Analysis
5.1.
Time Complexity:
5.2.
Space Complexity:
6.
Frequently Asked Questions
7.
Key Takeaways
Last Updated: Mar 27, 2024

Form a Number Using Bit Rotations of N having the Same Frequency of each Digit

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

 

Introduction

Data Structures play a vital role in our problem-solving skills. Consistency with an efficient learning approach can raise your bar in the programming world.

The problem is forming the number using bit rotations having the same frequency of each digit.

Before stepping into this problem, your concepts should be transparent regarding rotating a binary number in both directions(clockwise and anticlockwise).

 

Let’s move to our problem statement for more clarity.

Problem statement

 

We are given a number ‘n.’ We will aim to convert it into a binary representation and perform the rotations(anticlockwise or clockwise) every time until we get a number where all digits will have the same frequency.

If, after the rotations, no number can be found with the same frequency, then print -1.

 

Let’s clear this mess with the help of an example.

 

Example 1:

 

Input: n= 331

Output: 421

 

Explanation: The binary representation of ‘331’ will be 101001011. After performing anticlockwise or clockwise rotations, we will generate a number 421, in which each digit has frequency as ‘1’.

There is a possibility of more than one solution for a particular input, and you have to print any one of them.

 

Example 2:

 

Input: n = 424

Output: 106

 

Explanation: Here, the binary representation of ‘424’ will be 110101000. After performing the rotations, the number generated will be 106, where every digit has a frequency of ‘1’.

 

Now that we have understood the question, let’s move towards our approach and implementation.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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);
  }
}

 

Output

421

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

  1. 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).
     
  2. 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).
     
  3. 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!!!

 

Previous article
Count Total Set Bits in an Array
Next article
Maximize Bitwise AND of the array by replacing at most one element
Live masterclass