Flipping bits problem

The problem consists of converting a 32-bit (long in Java) unsigned int to binary and then flipping (1 -> 0, 0->1) the bits.

After the bits are reversed, to convert back to an unsigned int represented by a long in Java.

The catch is that if the number is low, like 9 converted to binary, we have 1001.

We need to append 0s in front of the 4 digits until we reach 32 bits,

      while (binary.length() < 32) {
            binary = "0" + binary;
       }
              

and then

To iterate through each bit and "flip the bits"

      StringBuilder sb = new StringBuilder();
      for (char c : binary.toCharArray()){
        char reversedBit  = c == '1'? '0':'1';
        sb.append(reversedBit);
      }
      return Long.parseLong(sb.toString(), 2);         

At the end, we return the value.

The complete method is this:

    public static long flippingBits(long n) {
      String binary = Long.toBinaryString(n);
      
      while (binary.length() < 32) {
            binary = "0" + binary;
       }
      
      StringBuilder sb = new StringBuilder();
      for (char c : binary.toCharArray()){
        char reversedBit  = c == '1'? '0':'1';
        sb.append(reversedBit);
      }
      return Long.parseLong(sb.toString(), 2); 
    }        

Java doesn’t support unsigned integers (unsigned int, unsigned long, etc.) primarily for design reasons like simplicity, security, and platform independence.

Why time and space complexity are both O(1)

Time complexity

1. Long.toBinaryString(n)

Takes up to O(log n) time since it generates a binary string with at most 32 characters.

2 . while (binary.length() < 32)

• Worst case: Binary string is short (e.g. "1") -> up to 31 iterations.
• Each iteration prepends a character: 0 for each prepend, total up to 32 chars
• Because we have a fixed length of 32 chars, we have a constant runtime for this loop.

3. binary.toCharArray() and loop over 32 bits → O(32) => O(1)

4. sb.append(...) → appending 32 times → O(32) => O(1)

5. Long.parseLong(..., 2) → parses a 32-char binary string → O(32) => O(1)

Because all operations are with fixed length, we have Time complexity of O(1)

Space complexity

• binary: a string of length ≤ 32 → O(1)
• StringBuilder: also holds 32 chars → O(1)
• Temporary char array in .toCharArray() → O(1)

We don't have Data Structures that grow with the input size,

or arrays allocated with size n,

or recursion calls using the call stack. (for 5 nested calls we have O(n) space complexity),

That's why we have a space complexity of O(1).