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

Arrays3

Q3. You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum.
EXAMPLE
input: {2, -8, 3, -2, 4, -10}
output: 5 [ eg, {3, -2, 4} ]

Answer:

public class Arrays3 {
    public static int largestContinuousSum(int[] a) {
        int maxsum = 0;
        int sum = 0;

        for (int i = 0; i < a.length; i++) {
            sum += a[i];
            // if current sum is greater than maxsum then update maxsum
            if (sum > maxsum) {
                maxsum = sum;
            } else if (sum < 0) { // else if sum goes below zero reset sum and
                                  // start adding sum from new index
                sum = 0;
            }
        }
        return maxsum;
    }

    public static void main(String[] args) {
        int[] arr1 = { 2, -8, 3, -2, 4, -10 };
        int[] arr2 = { 6, -8, 3, -2, 4 };
        int[] arr3 = { -8, 6, 3, -2, 4 };

        System.out.println(largestContinuousSum(arr1));
        System.out.println(largestContinuousSum(arr2));
        System.out.println(largestContinuousSum(arr3));
    }
}

Arrays2

Q2. Write code to remove the duplicate characters in a string without using any additional buffer.
Answer:
* As strings are immutable in java so we have to generate a new string.

import java.util.HashSet;
import java.util.Set;

public class Arrays2 {
    public static String removeDuplicates(String s) {
        if (s == null) {
            return null;
        }

        StringBuilder r = new StringBuilder("");
        Set<Character> chars = new HashSet<Character>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!chars.contains(c)) {
                chars.add(c);
                r.append(c);
            }
        }
        return r.toString();
    }

    public static void main(String[] args) {
        String s1 = "aaaa";
        String s2 = "aabbcc";
        String s3 = "abcd";
        String s4 = "ababab";
        String s5 = "";
        String s6 = null;
        String s7 = "a  b  c";

        System.out.println(removeDuplicates(s1));
        System.out.println(removeDuplicates(s2));
        System.out.println(removeDuplicates(s3));
        System.out.println(removeDuplicates(s4));
        System.out.println(removeDuplicates(s5));
        System.out.println(removeDuplicates(s6));
        System.out.println(removeDuplicates(s7));
    }
}

Arrays1

Q1. Suppose we have an array a1, a2, ..., an, b1, b2, ..., bn. Implement an algorithm to change this array to a1, b1, a2, b2, ..., an, bn without using extra space.

Answer:

public class Arrays1 {
    public void shuffleArray(int[] a) {
        int n = a.length / 2;

        for (int i = 0, j = 1; i < n; i++, j += 2) {
            // right rotate sub-array arr[j] to arr[N+i]
            rightRotate(a, j, n + i);
        }
    }

    // rotate right an array
    private void rightRotate(int[] a, int first, int last) {
        int lastItem = a[last];
        for (int i = last; i > first; i--) {
            a[i] = a[i - 1];
        }
        a[first] = lastItem;
    }

    public void shuffleArrayRecursive(int[] a) {
        shuffleArrayRecursive(a, 0, a.length - 1);
    }

    private void shuffleArrayRecursive(int[] a, int p, int q) {
        if (p == q) {
            return;
        }

        int r = (p + q) / 2;
        swap(a, (p + r) / 2 + 1, r, r + 1, (r + q) / 2);
        shuffleArrayRecursive(a, p, r);
        shuffleArrayRecursive(a, r + 1, q);
    }

    // swap elements from p to q with elements from r to s
    private void swap(int[] a, int p, int q, int r, int s) {
        for (int i1 = p, i2 = r; i1 <= q; i1++, i2++) {
            int temp = a[i1];
            a[i1] = a[i2];
            a[i2] = temp;
        }

    }

    public void printArray(int[] a) {
        System.out.println();
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    public static void main(String[] args) {
        Arrays1 obj = new Arrays1();
        int[] a = { 1, 3, 5, 2, 4, 6 };
        obj.printArray(a);
        obj.shuffleArray(a);
        obj.printArray(a);

        int[] b = { 1, 3, 5, 7, 2, 4, 6, 8 };
        obj.printArray(b);
        obj.shuffleArrayRecursive(b);
        obj.printArray(b);
    }
}

• Recursive solution is working correctly only if n is even.
• Order of complexity for rotate function = O(n²)
• Order of complexity for recursive function = O(nlogn)

Mathenatics16

Q16. In Excel sheet rows are marked using integer numbers like 1,2,3 but the columns are marked using characters. Like A, B and C.
so here column 0 = A (assuming column starting with 0)
column 1 = B
column 25 = Z
column 26 = AA
column 100 = CW
Write a program to give the string representation of column for given integer.

Some test data: 

A - Z will be represented by 0-25
AA - ZZ will create 26*26 = 676 more numbers.
so AA-ZZ will be from 26 - 701
Number - Column name
701        -  ZZ
702        -  AAA
703        - AAB
[Question was asked in MS interview. Order of complexity was also asked for the code.]

Answer:

public class Mathematics16 {
    public static String convertToExcelColumn(int n) {
        if (n < 0) {
            return "";
        }

        int m = n % 26;
        StringBuilder sb = new StringBuilder();
        sb.append((char) ('A' + m));
        n/=26;

        while (n > 26) {
            m = n % 26;
            sb.insert(0, (char) ('A' + m - 1));
            n /= 26;
        }

        if (n > 0) {
            sb.insert(0, (char) ('A' + n - 1));
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        for (int i = 0; i <= 704; i++) {
            System.out.println(i + " -> " + convertToExcelColumn(i));
        }
    }
}

• Order of complexity of above algo = number of chars in excel column  name

                                                                   = O(log₂₆n)

Mathematics15

Q15. Design an algorithm to find the nth number such that the only prime factors are 3, 5, and 7.
Answer:

import java.util.LinkedList;
import java.util.Queue;

public class Mathematics15 {
    public static int magicNumber(int n) {
        Queue<Integer> q3 = new LinkedList<Integer>();
        Queue<Integer> q5 = new LinkedList<Integer>();
        Queue<Integer> q7 = new LinkedList<Integer>();

        if (n <= 0) {
            return 0;
        }

        // 1st magic number is 1 = 3^0*5^0*7^0
        int val = 1;
        q3.add(3);
        q5.add(5);
        q7.add(7);

        // we’ve done one iteration already for 1st
        // magic number
        for (int i = 2; i <= n; i++) {
            val = min(q3.peek(), q5.peek(), q7.peek());
            if (val == q3.peek()) {
                q3.poll();
                q3.add(val * 3);
                q5.add(val * 5);
                q7.add(val * 7);
            } else if (val == q5.peek()) {
                q5.poll();
                q5.add(val * 5);
                q7.add(val * 7);
            } else {
                // now it must must be from q7
                q7.poll();
                q7.add(val * 7);
            }
        }
        return val;
    }

    // function to find min of 3 integers
    public static int min(int a, int b, int c) {
        int min = a;
        if (b < a)
            min = b;
        if (c < min)
            min = c;
        return min;
    }

    public static void main(String[] args) {
        for (int i = 1; i <= 20; i++) {
            System.out.println("Magic Number" + i + "= " + magicNumber(i));
        }
    }
}

Mathematics14

Q14. Find the digital root  of a given number.
Digital Root: (also repeated digital sum) of a number is the (single digit) value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached.

For example, the digital root of 65,536 is 7, because 6+5+5+3+6 = 25 and 2+5 = 7.

Answer:

public class Mathematics14 {
    public static int getDigitalRoot(int n) {
        if (n <= 0) {
            System.out.println("Digital root is not defined for negative numbers");
            return 0;
        }

        int digitalRoot = n % 9;
        if (digitalRoot == 0) {
            return 9;
        }
        return digitalRoot;
    }

    public static void main(String[] args) {
        System.out.println(getDigitalRoot(15));
        System.out.println(getDigitalRoot(181));
        System.out.println(getDigitalRoot(72));
        System.out.println(getDigitalRoot(65536));
    }
}

Mathematics13

Q13. Write an algorithm which computes the number of trailing zeros in n factorial.
Answer:

public class Mathematics13 {
    public static int getTrailingZeroes(int n) {
        if (n < 0) {
            System.out.println("Factorial is not defined for negative numbers");
            return 0;
        }

        int count = 0;
        for (int i = 5; n / i > 0; i *= 5) {
            count += n / i;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println("Number of trailing zeroes in 10! : "
                + getTrailingZeroes(10));
        System.out.println("Number of trailing zeroes in 100! : "
                + getTrailingZeroes(100));
        System.out.println("Number of trailing zeroes in 125! : "
                + getTrailingZeroes(125));
    }
}

Mathematics12

Q12. Return the reverse of a given integer.
Answer: This question is mostly asked for C/C++ language, but in java it is easy to just make use of string functions.

public class Mathematics12 {
    public static int reverseNumber(int n) {
        String number = ((Integer) n).toString();
        String reverse = new StringBuilder(number).reverse().toString();
        return Integer.parseInt(reverse);
    }

    public static void main(String[] args) {
        System.out.println(reverseNumber(123));
        System.out.println(reverseNumber(654));
    }
}

Mathematics11

Q11. Print prime factors of a given number. e.g. for 54 Prime factors: 2, 3, 3, 3.
Answer:

import java.util.ArrayList;
import java.util.List;

public class Mathematics11 {
    public static int[] getPrimeFactors(int n) {
        List<Integer> factors = new ArrayList<Integer>();

        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                factors.add(i);
                n /= i;
            }
        }

        if (n > 1) {
            factors.add(n);
        }

        int[] primeFactors = new int[factors.size()];

        int i = 0;
        for (Integer p : factors) {
            primeFactors[i++] = p;
        }

        return primeFactors;
    }

    public static void main(String[] args) {
        for (int i = 2; i <= 20; i++) {
            System.out.print("Prime factors for " + i + ": ");
            for (int n : getPrimeFactors(i)) {
                System.out.print(n + " ");
            }
            System.out.println();
        }
    }
}

Mathematics10

Q10. Find LCM and GCD of given 2 numbers. Try both recursive and iterative function for GCD.
Answer:

public class Mathematics10 {
    public static int getGCDRecursive(int m, int n) {
        if (n == 0) {
            return m;
        } else {
            return getGCDRecursive(n, m % n);
        }
    }

    public static int getGCDIterative(int m, int n) {
        if (n == 0) {
            return m;
        } else {
            while (n != 0) {
                int remainder = m % n;
                m = n;
                n = remainder;
            }
            return m;
        }
    }

    public static int getLCM(int m, int n) {
        return (m * n) / getGCDRecursive(m, n);
    }

    public static void main(String[] args) {
        System.out.println("GCD of 40, 10 = " + getGCDRecursive(40, 10));
        System.out.println("GCD of 24, 40 = " + getGCDRecursive(24, 40));

        System.out.println("GCD of 40, 10 = " + getGCDIterative(40, 10));
        System.out.println("GCD of 24, 40 = " + getGCDIterative(24, 40));

        System.out.println("LCM of 40, 10 = " + getLCM(40, 10));
        System.out.println("LCM of 24, 40 = " + getLCM(24, 40));
    }
}

Mathematics9

Q9. Write a method to generate the nth Fibonacci number. Try both recursive and iterative function.
Fibonacci Function: f(0) = 0, f(1) = 1, f(n) = f(n - 1) + f(n - 2)

Answer:

public class Mathematics9 {
    public static int fibonacciRecursive(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else if (n > 1) {
            return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
        } else {
            // return error code to show that Fibonacci is not
            // defined for given input
            return -1;
        }
    }

    public static int fibonacciIterative(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else if (n > 1) {
            int tn_2 = 0;
            int tn_1 = 1;
            int tn = 0;

            for (int i = 2; i <= n; i++) {
                tn = tn_1 + tn_2;
                tn_2 = tn_1;
                tn_1 = tn;
            }
            return tn;
        } else {
            // return error code to show that Fibonacci is not
            // defined for given input
            return -1;
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i <= 10; i++) {
            System.out.print(fibonacciRecursive(i) + " ");
        }

        System.out.println();

        for (int i = 0; i <= 10; i++) {
            System.out.print(fibonacciIterative(i) + " ");
        }
    }
}

Mathematics8

Q8. Write a method to get factorial of given integer? Try both recursive and iterative method.

Answer: 

public class Mathematics8 {
    public static int factorialRecursive(int n) {
        if (n < 0) {
            System.out.println("Factorial is not defined for negative numbers");
            return 0;
        }

        if (n == 0) {
            return 1;
        }
        return n * factorialRecursive(n - 1);
    }

    public static int factorialIterative(int n) {
        if (n < 0) {
            System.out.println("Factorial is not defined for negative numbers");
            return 0;
        }

        int fact = 1;
        for (int i = 1; i <= n; i++) {
            fact *= i;
        }
        return fact;
    }

    public static void main(String[] args) {
        System.out.println(factorialRecursive(0));
        System.out.println(factorialRecursive(-11));
        System.out.println(factorialRecursive(5));
        System.out.println(factorialRecursive(10));

        System.out.println(factorialIterative(0));
        System.out.println(factorialIterative(-11));
        System.out.println(factorialIterative(5));
        System.out.println(factorialIterative(10));
    }
}

Mathematics7

Q7. Randomly generate a weighted index for a given array. The probability for bigger number should be more than smaller number.

For example: if given array is {15, 18, 17, 15, 35} then generate a random index (from 0 to 4), but since 35 is the biggest number so probability of getting index 4 should be maximum. Probability should also be proportional to the number like if probability to generate index for number 50 is p then probability to generate index for number 25 should be p/2.

Answer:

• First take a small problem suppose array is {1,2,3}
• Now if probability for getting 1 is p, then probability for getting 2 is 2p and probability for getting 3 is 3p.
• Sum all numbers of the array. 1+2+3 = 6. 
• Generate a random number from 1 to 6. 
• Return 1 if generated number is 1. Here probability for getting 1 is 1/6.
• Return 2 if generated number is 2 or 3. Here probability for getting 2 is 2/6.
• Return 3 if generated number is 4 or 5 or 6. Here probability for getting 3 is 3/6.

import java.util.Random;

public class Mathematics7 {
    public int getRandomIndex(int[] array) {
        int sum = 0;
        for (int i = 0; i < array.length; i++) {
            sum += array[i];
        }

        int randomNumber = new Random().nextInt(sum);
        int currentSum = 0;
        int index;
        for (index = 0; index < array.length; index++) {
            currentSum += array[index];
            if (randomNumber < currentSum)
                break;
        }
        return index;
    }

    public static void main(String args[]) {
        Mathematics7 w = new Mathematics7();
        int array[] = { 15, 18, 17, 14, 35 };
        int count[] = new int[array.length];

        // generate random index 100 times for the array
        // the biggest number should get maximum chances
        for (int i = 0; i < 100; i++) {
            int randomIndex = w.getRandomIndex(array);
            count[randomIndex]++;
        }

        for (int i = 0; i < count.length; i++)
            System.out.println("array[" + i + "]= " + array[i] + "->" + count[i]);
    }
}

Mathematics6

Q6. Find the square root of given number n without using Math.sqrt() function and multiplication operation? Return the largest integer less than or equal to square root of given number n. For example:
getSquareRoot(16) = 4
getSquareRoot(17) = 4
getSquareRoot(25) = 5
getSquareRoot(26) = 5 
getSquareRoot(36) = 6

Answer: 

• Hint: Sum of 1st n odd integers = square of n.
• Example:
• 1 = 1 = sqr(1)
• 1 + 3 + 5 = 9 = sqr(3)
• 1 + 3 + 5 + 7= 16 = sqr(4)

public class Mathematics6 {
    public static int getSquareRoot(int n) {
        int squareRoot = 0;
        int sum = 0;
        int oddNumber = 1;

        while (sum <= n) {
            sum += oddNumber;
            oddNumber += 2;
            squareRoot++;
        }
        return (squareRoot-1);
    }

    public static void main(String[] args) {
        System.out.println(getSquareRoot(12));
        System.out.println(getSquareRoot(624));
        System.out.println(getSquareRoot(625));
        System.out.println(getSquareRoot(626));
    }
}

Mathematics5

Q5. Print all prime numbers from 1 to given number n?

Answer: 

• Brute force algo: we can iterate from 1 to n, check if a number is prime (using function from Mathematics-4), but this is not optimal solution.
• Optimal solution: Sieve of Eratosthenes 

public class Mathematics5 {
    public static void printPrimes(int n) {
        // maintain an boolean array to mark prime numbers
        boolean[] isPrime = new boolean[n + 1];

        // initially assume all integers from 2 to n are prime
        // we know that 1 is not prime
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }

        // mark non-primes <= N using Sieve of Eratosthenes
        for (int i = 2; i * i <= n; i++) {
            // if i is prime, then mark multiples of i as non prime
            if (isPrime[i]) {
                for (int j = i; i * j <= n; j++) {
                    isPrime[i * j] = false;
                }
            }
        }

        // print all primes
        for (int i = 1; i <= n; i++) {
            if (isPrime[i])
                System.out.println(i);
        }
    }

    public static void main(String[] args) {
        printPrimes(100);
    }
}

Mathematics4

Q4. How to determine if a given number is prime?
Answer: 

public class Mathematics4 {
    public static boolean isPrime(int num) {
        // return false if num is 1
        if (num == 1) {
            return false;
        }

        // return false if num is greatrer than 2 and even
        if ((num > 2) && ((num & 1) == 0)) {
            return false;
        }

        int squareRootOfNum = (int) (Math.sqrt(num));
        for (int i = 2; i <= squareRootOfNum; i++) {
            if ((num % i) == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        for (int i = 1; i <= 11; i++) {
            System.out.println(i + " is prime: " + isPrime(i));
        }
    }
}
  

• Orde of complexity for above algo: 
• O(1) for even numbers 
• O(sqrt(n)) if n is odd
  

Mathematics3

Q3. How to count number of set bits in an integer?

Answer:
* Reducing an integer number by 1 always set the rightmost bit off. We can start reducing 1 till we get zero.

public class Mathematics3 {
    public static int counBits(int num) {
        if (num == 0)
            return 0;

        int count = 1;

        while ((num = (num & (num - 1))) != 0) {
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println("Number of 1 bits in 0 = " + counBits(0));
        System.out.println("Number of 1 bits in 1 = " + counBits(1));
        System.out.println("Number of 1 bits in 7 = " + counBits(7));
        System.out.println("Number of 1 bits in 15 = " + counBits(15));
        System.out.println("Number of 1 bits in 127 = " + counBits(127));
        System.out.println("Number of 1 bits in -1 = " + counBits(-1));
    }
}

Mathematics2

Q2. How to find if a number is power of 2?
Answer:
* Binary representation of a number which is power of 2 will have only 1 bit on.
* See below some 4 bits representation of numbers
    1 = 0001
    2 = 0010
    4 = 0100
* We need to check the binary representation of the number will contain only 1 bit on.

public class Mathematics2 {
    public static boolean isPowerOfTwo(int number) {
        if((number & (number - 1)) == 0 ){
            return true;
        }
        return false;
    }
  
    public static void main (String[] args) {
        System.out.println(isPowerOfTwo(1));
        System.out.println(isPowerOfTwo(2));
        System.out.println(isPowerOfTwo(16));
        System.out.println(isPowerOfTwo(18));
    }
}

Mathematics1

Q1. How to find if a number is even or odd?
Answer:

public class Mathematics1 {
    // return true if number is divisible by 2 else return false
    public static boolean isEven(int number) {
        if (number % 2 == 0) {
            return true;
        }
        return false;
    }

    // same function without using modulus operator
    // return true if last bit is 0 in number else return false
    public static boolean isEvenWithOutModulusOperator(int number) {
        if ((number & 1) == 0) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(isEven(4));
        System.out.println(isEven(5));

        System.out.println(isEvenWithOutModulusOperator(14));
        System.out.println(isEvenWithOutModulusOperator(15));
    }
}

Frequently asked programming questions

Here I am going to post some of the frequently asked programming questions and answers in java language. I am initially going to post some easy questions and solutions in java based on mathematics.