Math

In this section we will talk about math related interview questions, and some typical techniques to solve them.

Number bases

It's important to understand different bases of the numbers, and to be able to convert between them. For programmers, most important bases are 2 (binary), 8, and 16.

The following code converts an integer number to its binary representation. Note how we return result as a string, and how we treat non-positive numbers separately:

String convertToBinary(int x) {
    if (x == 0) return "0";
    if (x < 0)  return "-" + convertToBinary(-x);

    StringBuilder result = new StringBuilder();
    while (x > 0) {
        result.append(x % 2);
        x /= 2;
    }
    return result.reverse().toString();
}

System.out.println(convertToBinary(2));  // prints 10
System.out.println(convertToBinary(0));  // prints 0
System.out.println(convertToBinary(-7)); // prints -111
System.out.println(convertToBinary(13)); // prints 1101

You can modify the code above to convert integers to any base – just replace 2s with the base you want (of course, for bases bigger than 10 you will also need to somehow accomodate non-digit symbols).

The following code converts binary number represented as a string to the base 10 integer. For simplicity here we assume that numbers are non-negative, and fit into an int type:

int convertFromBinary(String binary) {
    int result = 0;
    for (int i = 0; i < binary.length(); i++)
        result = result * 2 + binary.charAt(i) - '0';        
    return result;
}

System.out.println(convertFromBinary("10"));   // prints 2
System.out.println(convertFromBinary("0"));    // prints 0
System.out.println(convertFromBinary("1101")); // prints 13

You can practice base conversion on the following problem:

Know your variable types

This is not a purely math topic, but it's an important related one. You should know your language types well: ints, longs, doubles, and so on. What are the limits of each type? How many bits and memory does each one take? When should you use ints and when longs? Knowing answers to these questions is essential, and will allow you to use the right variable types every time.

You can also read how numbers are represented in the computer. How are negative numbers and floating point numbers represented as binary numbers?

Binary expontentiation

How to calculate something like X^P? Of course, you can just write a loop which will work in O(P):

// calculates 7^20
long res = 1;
for (int i = 0; i < 20; i++)
    res *= 7;
System.out.println(res); // prints 79792266297612001

Or you can use your language's built-in library, but it can be not that precise for large numbers:

// calculates 7^20
System.out.println((long) Math.pow(7, 20));             // prints 79792266297612000 (!)
System.out.println((long) Math.round(Math.pow(7, 20))); // prints 79792266297612000 as well

But actually, you can calculate X^P in O(log(P)) time with the binary exponentiation technique. This is roughly based on the fact that X^2K = (X²)^K, so you can divide an even exponent by 2 in just one operation.

You can read more about binary exponentiation on Cp-Algorithms or in the Competitive Programmer’s Handbook, and here is the implementation of the idea:

// we assume power p is non-negative 
long binaryPow(long x, long p) {
  long result = 1;
  while (p > 0) {
      if (p % 2 == 0) {
          x = x * x;
          p /= 2;
      } else {
          result = result * x;
          p--;
      }
  }
  return result;
}

System.out.println(binaryPow(7, 20)); // prints 79792266297612001

Note that for the big numbers the result can be bigger than maximum long value. In that case, you can calculate the result in doubles, or modulo some number.

You can practice this method on the following problem:

Prime numbers

A number is called prime if it's bigger than one, and doesn't have any divisors other than 1 and itself. For example, the first five prime numbers are 2 (only divisors are 1 and 2), 3, 5, 7, and 11.

The following code tests if the number is prime. The idea here is that if a number has a divisor bigger than its square root, than it also has a divisor less than a square root: if X = A × B, then either A or B are less than or equal to the square root of X. So we can only check divisors up to the square root of a number, and the time complexity is O(sqrt(X)):

boolean isPrime(int x) {
    if (x <= 1) return false;
    
    // note how we use i * i <= x to iterate up to the square root. 
    // this method is more precise than for example i <= Math.sqrt(x)
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) 
            return false;

    return true;
}

The following code finds all prime numbers up to some number N. Here we use so called Sieve of Eratosthenes. The idea is that every non-prime number has at least one prime divisor, so we can just mark everything that is divided by some prime number as non-prime.

What's more interesting here is the time complexity. We can have the following upper bound: the inner loop is executed not more than N + (N / 2) + (N / 3) + ... times. We can rewrite it as N × (1 + 1/2 + 1/3 + ...), and with the formula for the sum of harmonic series, we will get O(NlogN) upper bound on the runtime.

final int n = 1000;
boolean[] isPrime = new boolean[n];
Arrays.fill(isPrime, true);

isPrime[0] = isPrime[1] = false;
for (int i = 2; i < n; i++) {
    if (isPrime[i]) {
        for (int j = 2 * i; j < n; j += i)
            isPrime[j] = false;
    }
}

// prints all prime numbers up to n.
for (int i = 0; i < n; i++)
    if (isPrime[i])
        System.out.println(i);

To read in more details about prime numbers and the algorithms mentioned above, check out the following resources:

1. CP-Algorithms. Primality tests
2. CP-Algorithms. Sieve of Eratosthenes
3. Competitive Programmer’s Handbook – check out the chapter on number theory.
4. Introduction to Algorithms has a chapter on number theory, if you want to dive deeper.

You can practice finding prime numbers on the following problem:

Number factorization and divisors

The following code finds all divisors of the number X in O(sqrt(X)). The idea here is again that if X = A × B, then either A or B are less than or equal to the square root of X:

final int X = 48;
List<Integer> divisors = new ArrayList<>();

for (int i = 1; i * i <= X; i++) {
    if (X % i == 0) {
        divisors.add(i);
        if (X / i != i) divisors.add(X / i);
    }
}

// sort and print all divisors of X in an increasing order
Collections.sort(divisors);
System.out.println(divisors); // [1, 2, 3, 4, 6, 8, 12, 16, 24, 48]

The following code finds all prime divisors and factorization of X, again in O(sqrt(X)) time:

final int X = 120;
List<Integer> primeDivisors = new ArrayList<>();
List<Integer> factorization = new ArrayList<>();

int currentNum = X;
for (int i = 2; i * i <= currentNum; i++) {
    if (currentNum % i == 0) {
        primeDivisors.add(i);
        while (currentNum % i == 0) {
            factorization.add(i);
            currentNum /= i;
        }                
    }
}
if (currentNum > 1) {
    primeDivisors.add(currentNum);
    factorization.add(currentNum);
}

// prints factorization of X
Collections.sort(factorization);
System.out.println(factorization); // [2, 2, 2, 3, 5], as 2 * 2 * 2 * 3 * 5 = 120

// sort and print all prime divisors of X
Collections.sort(primeDivisors);
System.out.println(primeDivisors); // [2, 3, 5]

You can read more about number factorization on CP-Algorithms or in Competitive Programmer’s Handbook.

To practice this, you can solve the following problem:

More practice problems

Here are some more good math related problems. Some of them don't require any particular algorithm, and more of a brain teasers, but they are good practice as well: