jacl
BAN USERAgree with above.
Giving an actual code below which uses String to represent both base2 and base4 numbers. Given this implementation, a clarification can be raised for leading zeros (if they need to be printed or not).
package base2tobase4;
public class Main {
public static boolean isValidInput(String b2) {
// Check if null/empty
if (b2 == null || b2.isEmpty()) {
return false;
}
// Check if all characters are just 1s and 0s
int b2Length = b2.length();
for (int i = 0; i < b2Length; i++) {
if (b2.charAt(i) != '1' && b2.charAt(i) != '0') {
return false;
}
}
return true;
}
public static String convertB2toB4(String b2) {
if (!isValidInput(b2)) {
// Invalid input
return null;
}
// Do the conversion
// The idea is to group the bits into two's since the binary representation of a base4 number is 2 bits.
// (actually, other powers of 2 follows. e.g. 3 bits for base8, 4 bits for base16, 5 bits for base 32, etc.)
StringBuilder result = new StringBuilder();
int b2Length = b2.length();
for (int i = b2Length - 1; i >=0; i = i - 2) {
int currNumber = 0;
// First bit
if (b2.charAt(i) == '1') {
currNumber++;
}
// Second bit
if (i > 0 && b2.charAt(i - 1) == '1') {
currNumber += 2;
}
// Convert the resulting number to String
result.append(String.valueOf(currNumber));
}
// Reverse the string since we processed from right to left
return result.reverse().toString();
}
public static void main(String[] args) {
/*
* Test cases
* 1. Null input - invalid case
* 2. Empty String - invalid case
* 3. Invalid binary number - invalid case
* 4. 1 bit binary number (0) - normal case
* 5. 1 bit binary number (1) - normal case
* 6. 2 bit binary number (10) - normal case
* 7. 2 bit binary number (11) - normal case
* 8. n bit binary number - normal case
* 9. binary number with even number of bits - normal case to test the loop
* 10. binary number with odd number of bits - normal case to test the loop specifically the i - 1 part
* 11. leading zeros
*/
System.out.println("1. " + convertB2toB4(null));
System.out.println("2. " + convertB2toB4(""));
System.out.println("3. " + convertB2toB4("1234"));
System.out.println("4. " + convertB2toB4("0"));
System.out.println("5. " + convertB2toB4("1"));
System.out.println("6. " + convertB2toB4("10"));
System.out.println("7. " + convertB2toB4("11"));
System.out.println("8. " + convertB2toB4("11101101110011"));
System.out.println("9. " + convertB2toB4("1111"));
System.out.println("10. " + convertB2toB4("11111"));
System.out.println("11. " + convertB2toB4("0000000000111111"));
}
}
Another O(n logn) time and O(n) space solution. Please correct me if there are issues.
- jacl August 08, 2013