Dede Blog: just another Software Development Engineer

We have already seen in the article “Spotify Puzzles: solving ReverseBinary in Java with just 1 line of code” how to solve the Reverse Binary puzzle proposed by Spotify using the methods offered by Integer and StringBuilder classes to manipulate objects, without applying any conversion logic between the two numeral systems.
This time, we will implement an alternative solution that addresses the problem from the conceptual point of view, implementing the conversion algorithms from a decimal number to its relative binary representation and vice versa.

To convert a decimal to binary we have to iteratively divide by 2 the number until 0 is reached and then take the remainders of each division in reverse order.
The following example shows the process, finding the binary representation of the decimal number 13, provided as test input for the puzzle:

In our case, we can just avoid to revert the remainders and simply take them in the order they are generated to have the binary sequence reversed. So we can write a method decToBinInverted that takes as input an int and returns its binary representation already reversed:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class ReverseBinary {

    private static ArrayList decToBinInverted(int n)
    {
        ArrayList num = new ArrayList();
        while (n > 0)
        {
            num.add(n%2);
            n=n/2;
        }

        return num;
    }

    public static void main(String[] args){
        int n = 0;
        ArrayList num = null;
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            n = Integer.parseInt(br.readLine());
        } catch (Exception e) {
           System.err.println("Error:" + e.getMessage()); }

        num = decToBinInverted(n);

        for (int i: num)
            System.out.print(i);
    }
}

We provide now as input again the value 13 and let’s see what the output printed by the program will be:

INPUT
13
OUTPUT
1011

To perform the opposite conversion and to convert back a binary sequence in a decimal number is sufficient to multiply each bit of the sequence by increasing powers of 2 starting from the least significant bit, and then to sum up the values obtained from each bit.
The following figure shows the conversion of the binary string previously obtained:

Let’s proceed with the implementation of this logic in our program. We create another method called binToDec that takes as input the array of bits and returns the equivalent decimal int.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class ReverseBinary {

    private static ArrayList decToBin(int n)
    {
        ArrayList num = new ArrayList();
        while (n > 0)
        {
            num.add(n%2);
            n=n/2;
        }

        return num;
    }

    private static int binToDec(ArrayList num){
        int n=0;
        int exp = num.size()-1;

        for(int i : num) {
            n += i * Math.pow(2, exp);
            exp--;
        }

        return n;
    }

    public static void main(String[] args){
        int n = 0;
        ArrayList num = null;
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            n = Integer.parseInt(br.readLine());
        } catch (Exception e) {
            System.err.println("Error:" + e.getMessage()); }

        num = decToBin(n);

//      for (int i: num) {
//          System.out.print(i);
//      }

        System.out.println(binToDec(num));
    }
}

In this case, we calculated the exponent for the most significant bit and we went back to last bit, decreasing each time the exponent to which raise 2 before multiply it by the bit.

Let’s try to run the program against the two test cases provided with the puzzle:

INPUT
13
OUTPUT
11

INPUT
47
OUTPUT
61

Submitting the program to Spotify for verification, we get also with this version a positive feedback.