Leetcode 365. Water and Jug Problem

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

• Fill any of the jugs completely with water.
• Empty any of the jugs.
• Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1: (From the famous “Die Hard” example)

Input: x = 3, y = 5, z = 4
Output: True

Example 2:

Input: x = 2, y = 6, z = 5
Output: False

Analysis:

Very basic math problem. To understand it, we need to find whether ax + by = z.
Then solution is that z can be divided by the greatest common divisor (gcd).

Code is below:

public class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        
        //limit brought by the statement 
        // that water is finallly in one or both buckets
        if (x + y < z) {
            return false;
        }
        
        // case x/y to be 0
        if (x == z || y == z || x + y == z) {
            return true;
        }
        
        return z % gcd(x, y) == 0;
        
    }
    
    public int gcd(int x, int y) {
        if (y == 0) {
            return x;
        }
        
        return gcd(y, x % y);
    }
}

Leetcode 258. Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

Hint:

1. A naive implementation of the above process is trivial. Could you come up with other methods?

2. What are all the possible results?

3. How do they occur, periodically or randomly?

4. You may find this Wikipedia article useful.

Analysis:

Go to the link and find the common solutions for digital root: https://en.wikipedia.org/wiki/Digital_root

dr(n) = 1 + (n – 1) mod 9

原理10 % 9 或者 100 % 9都等于 1 % 9。举个例子n = abc = a  * 100 + b * 10 + c，那么 (a*100 + b * 10 + c) % 9 = (a + b + c) % 9。由此n == 0时，result = 0， n % 9 == 0时， 说明a + b + c = 9，我们返回9，对于其他数字， (a + b + c)等于res % 9。

Code is below:

public class Solution {
    public int addDigits(int num) {
        // O(1)
        return 1 + (num - 1) % 9;
    }
}

Leetcode 168 & 171. Excel Sheet Column Title / Number

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB

Analysis:
当n > 0时， 假如n % 26 == 0，则n为26的倍数，要转换为’Z’插入队首，之后n = n / 26 – 1， 假如n % 26 != 0， 则使用一般方法计算字符，int c = ‘A’ + n % 26 – 1， 之后 n /= 26。

Time complexity: O(n)
Space complexity: O(1)

Code is below:

public class Solution {
    public String convertToTitle(int n) {
        // O(n)
        
        if (n <= 0) {             return "";         }                  StringBuilder sb = new StringBuilder();                  while (n > 0) {
            if (n % 26 == 0) {
                sb.insert(0, 'Z');
                n = n / 26 - 1;
            } else {
                int c = 'A' + n % 26 - 1;
                sb.insert(0, (char) c);
                n /= 26;
            }
        }
        
        return sb.toString();
    }
}

Followup:
Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
…
Z -> 26
AA -> 27
AB -> 28

Analysis:
得到数字，其实就是把26进制的数转换为10进制的数。算法就是基本的进制转换方法，从后往前第n位的值乘上26^(n-1)。这里26进制数是1开始的，即A是1。

Time complexity: O(n)
Space complexity: O(1)

Code is below:

public class Solution {
    public int titleToNumber(String s) {
        // O(n)
        
        int res = 0;
        
        for (int i = 0; i < s.length(); i++) {
            res = res * 26 + (s.charAt(i) - 'A' + 1);
        }
        
        return res;
    }
}

Leetcode 204. Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n.

Analysis:

Sieve of Eratosthenes

To avoid time out. Basic idea:

Create a boolean array of size n and mark them true;

Go through the array, if find a prime number p, then start p^2, p^2+p, p^2+2p are all not prime number. Mark them to be false;

Go through the array again and count the prime number.

Note: 0 & 1 are not prime

(n/2+n/3+n/5…+n/比n小的最大素数） = n*(小于n的所有素数倒数的和） = O(n * log(logn))

Time complexity: O(nloglogn)

Space complexity: O(n)

Code is below:

public class Solution {
    public int countPrimes(int n) {
        // O(nloglogn) O(n)
        
        int count = 0;
        
        boolean[] prime = new boolean[n];
        
        for (int i = 2; i < n; i++) {
            prime[i] = true;
        }
        
        for (int i = 2; i * i < n; i++) {
            if (prime[i]) {
                // start from p^2, p^2+p, p^2+2p... not prime
                for (int j = i * i; j < n; j += i) {
                    prime[j] = false;
                }
            }
        }
        
        for (int i = 2; i < n; i++) {
            if(prime[i]) {
                count++;
            }
        }
        return count;
    }
}

Time out method:

public int countPrimes(int n) {
   int count = 0;
   for (int i = 1; i < n; i++) {
      if (isPrime(i)) count++;
   }
   return count;
}

private boolean isPrime(int num) {
   if (num <= 1) return false;
   // Loop's ending condition is i * i <= num instead of i <= sqrt(num)
   // to avoid repeatedly calling an expensive function sqrt().
   for (int i = 2; i * i <= num; i++) {
      if (num % i == 0) return false;
   }
   return true;
}

Leetcode 367. Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16
Returns: True

Example 2:

Input: 14
Returns: False

Analysis:

This problem is the same as the problem of leetcode 69: https://codebysteven.wordpress.com/2016/09/08/leetcode-69-sqrtx/

Basically we can just change the return value from double to be boolean.

Time complexity: O(logn)

Space complexity: O(1)

Below is the code:

public class Solution {
    public boolean isPerfectSquare(int num) {
        // O(logn) binary search
        
        // Corner case
        if (num == 0 || num == 1) {
            return true;
        }
        
        long start = 1;
        long end = num;
        
        while (start + 1 < end) {
            long mid = start + (end - start) / 2;
            
            if (mid * mid == num) {
                return true;
            } else if (mid * mid < num) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        return false;
    }
}

Leetcode 29. Divide Two Integers

Leetcode 29. Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

Analysis:

No multiplication, no division and mod operator! But we can use plus, minus, and shift operation : + – << >>

Shift operator

<< 1 is to multiply 2,e.g. 2<<1 = 4;
>> 1 is to divide 2 e.g. 8>>1 = 4;

Any number could be num=a_0*2^0+a_1*2^1+a_2*2^2+…+a_n*2^n.

So we can shift by 2 and minus the left until reach 0.

Time complexity: O(logn)

Space complexity: O(1)

Note: be very cautious about the corner case, especially the integer overflow.

Below is the code:

public class Solution {
    public int divide(int dividend, int divisor) {
        // Binary search O(logn)
        
        // Corner Case
        if (divisor == 0) {
            return dividend >= 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }
        
        if (dividend == 0) {
            return 0;
        }
        
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        
        boolean isNeg = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);
        
        long a = Math.abs((long) dividend);
        long b = Math.abs((long) divisor);
        
        int result = 0;
        
        while (a >= b) {
            int shift = 0;
            while (a >= (b << shift)) {
                shift++;
            }
            
            a -= b << (shift - 1);
            result += 1 << (shift - 1);
            
        }
        
        return isNeg ? -result : result;
    }
}

Leetcode 50 Pow(x, n)

Leetcode 50 Pow(x, n)

Implement pow(x, n).

Analysis:

The problem could be solved by O(n), as x ^ n equals to x * x * x….However, we want it to be more efficient. Then binary search comes to our mind, to divide the x ^ n to be x ^ (n / 2) * x ^ (n / 2).

Time complexity: O(logn)

The code is below:

public class Solution {
    /**
     * @param x the base number
     * @param n the power number
     * @return the result
     */
    public double myPow(double x, int n) {
        if (n > 0) {
            return pow(x, n);
        }
        // n < 0, return 1 / (x ^ (-n))
        return 1 / pow(x, -1 * n);
    }
    
    public double pow(double x, int n) {
        if (n == 0) {
            return 1;
        } 
        
        // Binary search 
        double k = pow(x, n / 2);
        if (n % 2 == 0) {
            return k * k;
        } else {
            return k * k * x;
        }
    }
}

Lintcode 366 Fibonacci

Lintcode 366 Fibonacci

Find the Nth number in Fibonacci sequence.

A Fibonacci sequence is defined as follow:

• The first two numbers are 0 and 1.
• The i th number is the sum of i-1 th number and i-2 th number.

The first ten numbers in Fibonacci sequence is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

Analysis:

This question is a mathematic formula, which defines the Fibonacci series. We can formalize is as:

• f(0) = 0
• f(1) = 1
• f(n) = f(n-1) + f(n-2)

This comes out the the first method.

Recursive method:

public static int fib(int n) {
	// Base case
	if (n == 0) {
		return 0;
	}

	if (n == 1) {
		return 1;
	}
	
	return fib(n - 1) + fib(n - 2);
}

Another method is the non-recursive method:

Non-recursive method:

// Non-recursive method
public static int fib1(int n) {
	// Base case
	if (n <= 1) {
		return n;
	}

	int n1 = 0;
	int n2 = 1;
	int n3 = 0;

	for (int i = 2; i <= n; i++) {
		n3 = n1 + n2;
		n1 = n2;
		n2 = n3;
	}

	return n2;
}

Note:

• we start from i = 2 
• Here do not return n3, and return n2, which has been assigned by the value we want, with n2 = n3.

Lintcode 9 Fizz Buzz

Lintcode 9 Fizz Buzz

Given number n. Print number from 1 to n. But:

when number is divided by 3, print “fizz”.
when number is divided by 5, print “buzz”.
when number is divided by both 3 and 5, print “fizz buzz”.

Analysis:

This is a very basic interview question for software engineer job. Basically, we can start by the most intuitive solutions:

• Check i is divided by 3, not divided by 5, print “fizz”
• Check i is divided by 5, not divided by 3, print “fuzz”
• Check i is both divided by 3 and 5, print “fizz buzz”
• Other numbers, print out the number

Disadvantages: too much % checking. We can improve this by starting from checking 3 and 5, then 5, then 3, then other numbers. The process is like:

• Check i is both divided by 3 and 5, print “fizz buzz”
• Check i is divided by 3, not divided by 5, print “fizz”
• Check i is divided by 5, not divided by 3, print “fuzz”
• Other numbers, print out the number

This Code is written in below:

for (int i = 1; i <= n; i++) {
	// Start from 15
	if (i % 15 == 0) {
		System.out.println("fizz buzz");
	} else if (i % 5 == 0) { // check with 5
		System.out.println("buzz");
	} else if (i % 3 == 0) { // check with 3
		System.out.println("fizz");
	} else { // print out other nums
		System.out.println(i);
	}
}

Alternative method:
In some interviews, the interviewer requires to use only two module and get the same result. To make this work, we can have a number k to indicate different situations. With different case of k, then print out different result.

for (int i = 1; i <= n; i++) {
	int k = 1;
	if (i % 3 == 0) k++;
	if (i % 5 == 0) k += 2;

	switch(k) {
		case 1:
			System.out.println(i);
			break;

		case 2:
			System.out.println("fizz");
			break;

		case 3:
			System.out.println("buzz");
			break;

		case 4:
			System.out.println("fizzbuzz");
			break;
	}
}

If we take the n to be 20, then the result is:

1
2
fizz
4
buzz
fizz
7
8
fizz
buzz
11
fizz
13
14
fizzbuzz
16
17
fizz
19
buzz