BitManipulation5

Q5. Write a function to swap a number in place without temporary variables.
Answer:

• It is not possible to write a function to swap primitive variables in Java, so I have created a class to wrap the int primitive.

class IntNumber {
    public int data;

    public IntNumber(int n) {
        this.data = n;
    }

    public String toString() {
        return "" + this.data;
    }
}

public class BitManipulation5 {
    public static void swap(IntNumber a, IntNumber b) {
        a.data = a.data ^ b.data;
        b.data = a.data ^ b.data;
        a.data = a.data ^ b.data;
    }

    public static void main(String[] args) {
        IntNumber a = new IntNumber(2);
        IntNumber b = new IntNumber(3);

        System.out.println("Before swapping a = " + a + " b = " + b);
        swap(a, b);
        System.out.println("After  swapping a = " + a + " b = " + b);
    }
}

BitManipulation4

Q4. Given a (decimal - e.g. 21.125) number N that is passed in as a string, print the binary representation (as a string). If the number cannot be represented accurately in binary, print "ERROR".

• Take care of all edge cases.
• Output only 4 significant binary digits after decimal

[This question was asked in Amazon online programming test]

Answer:

public class BitManipulation4 {
    static String decimalToBinary(String a) {
        if (a == null) {
            return "ERROR";
        }

        String[] number = a.split("\\.");
        if (number.length > 2) {
            return "ERROR";
        }

        int decimal = Integer.parseInt(number[0]);
        int fractional = 0;
        if (number.length == 2) {
            fractional = Integer.parseInt(number[1]);
        }

        String binary = Integer.toBinaryString(decimal);
        binary += ".";

        double d = Double.parseDouble("." + fractional);
        for (int i = 1; i <= 4; i++) {
            String t = ((int) 2 * d) >= 1 ? "1" : "0";
            binary += t;
            d = 2 * d;
            if (d >= 1) {
                d -= 1;
            }
        }
        return binary;
    }

    public static void main(String[] args) {
        System.out.println(decimalToBinary("23.2"));
        System.out.println(decimalToBinary("6.25"));
        System.out.println(decimalToBinary("23.2.3"));
        System.out.println(decimalToBinary(null));
        System.out.println(decimalToBinary("15"));
    }
}

BitManipulation3

Q3. Write a method to find the maximum of two numbers without using if-else or any other comparison operator.

Answer:

public class BitManipulation3 {

    public static int maximum(int a, int b) {
        int c = a - b;
        int k = (c >> 15) & 1;
        return a - k * c;
    }

    public static void main(String[] args) {
        System.out.println(maximum(5, 10));
        System.out.println(maximum(25, 10));
        System.out.println(maximum(-25, 10));
        System.out.println(maximum(-25, -10));
    }
}

BitManipulation2

Q2. Write a program to swap odd and even bits in integer, what is the minimum number of instructions required?
(eg, bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc).

Answer:

public class BitManipulation2 {
    public static int swapOddEvenBits(int n) {
        return (((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1));
    }
   
    public static void main(String[] args){
        // for 10: binary representation = 0000 0000 0000 1010
        // So output should be:                  0000 0000 0000 0101 (i.e 5)
        System.out.println(swapOddEvenBits(10));
        System.out.println(swapOddEvenBits(15));
    }
}

BitManipulation1

Q1. Write a function int BitSwapReqd(int A, int B) to determine the number of bits required to convert integer A to integer B.
input: 31, 14
output: 2

Answer:

public class BitManipulation1 {
    public static int requiredBitSwap(int a, int b) {
        int count = 0;
        for (int c = a ^ b; c != 0; c = c >> 1) {
            count += c & 1;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(requiredBitSwap(31, 14));
        System.out.println(requiredBitSwap(0, 15));
    }
}

Arrays5

Q5. An array contains all the integers from 1 to n except for one number which is missing (so there are n-1 elements in array). Write code to find the missing integer.
Answer:

public class Arrays5 {
    public static int findMissing(int[] a) {
        int n = a.length + 1;
        int sum = 0;

        for (int num : a) {
            sum += num;
        }

        int sigmaN = n * (n + 1) / 2;

        return sigmaN - sum;
    }

    public static int findMissing2(int[] a) {
        int n = a.length + 1;
        int missing = 1;
        for (int i = 2; i <= n; i++) {
            missing ^= i;
        }

        for (int num : a) {
            missing ^= num;
        }
        return missing;
    }

    public static void main(String[] args) {
        int[] a1 = { 1, 2, 4, 5, 6, 7 }; // 3 is missing from 1 to 7
        System.out.println(findMissing(a1));

        int[] a2 = { 1, 2, 3, 4, 5, 6, 7 }; // 8 is missing from 1 to 8
        System.out.println(findMissing(a2));

        System.out.println(findMissing2(a1));
        System.out.println(findMissing2(a2));
    }
}

Arrays4

Q4. Design an algorithm to find all pairs of integers within an array which sum to a specified value.

Answer:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Arrays4 {
    public static void printPairs(int[] a, int sum) {
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
        for (int i = 0; i < a.length; i++) {
            if (!m.containsKey(a[i])) {
                m.put(a[i], 0);
            }
            m.put(a[i], m.get(a[i]) + 1);
        }

        for (Integer data : m.keySet()) {
            int dataCount = m.get(data);
            // run the loop till we have count for data greater than 0
            while (dataCount > 0) {
                dataCount = m.get(data) - 1;
                m.put(data, dataCount);

                // find complement of data in the map
                int complement = sum - data;

                // if count for complement is greater than 0
                // then print a pair and reduce count for complement
                int complementCount = (m.get(complement) == null) ? 0 : m.get(complement);
                if (complementCount > 0) {
                    System.out.println(data + " " + complement);
                    complementCount = m.get(complement) - 1;
                    m.put(complement, complementCount);

                    // break the loop if there is no more complement
                    if (complementCount == 0) {
                        break;
                    }
                }
            }
        }
    }

    public static void printPairs2(int[] a, int sum) {
        Arrays.sort(a);

        int first = 0;
        int last = a.length - 1;

        while (first < last) {
            // if we get a pair. print it
            // increase first and decrease last
            if ((a[first] + a[last]) == sum) {
                System.out.println(a[first] + " " + a[last]);
                first++;
                last--;
            } else if ((a[first] + a[last]) < sum) {
                first++;
            } else {
                last--;
            }
        }
    }

    public static void main(String[] args) {
        int[] a1 = { 3, 4, 3, 4, 1, 6, 1, 6, 6 };
        System.out.println("Pairs of sum 7 for array a1: ");
        printPairs(a1, 7);

        int[] a2 = { 1, 2, 3, 4, 5 };
        System.out.println("Pairs of sum 7 for array a2: ");
        printPairs(a2, 7);

        int[] a3 = { 3, 3, 3, 3, 3 };
        System.out.println("Pairs of sum 6 for array a3: ");
        printPairs(a3, 6);

        System.out.println("Pairs of sum 7 for array a1: ");
        printPairs2(a1, 7);

        System.out.println("Pairs of sum 7 for array a2: ");
        printPairs2(a2, 7);

        System.out.println("Pairs of sum 6 for array a3: ");
        printPairs2(a3, 6);
    }
}