Chp17: Moderate

17.1 swap a number in place.(without temporary variables)

a = a ^ b;

b = a ^ b;

a = a ^ b;

17.3 Write a function which computes the number of trailing zeros in n factorial.

To count the number of zeros, we only need to count the pairs of multiples of 5 and 2. There will always be more multiples of 2 than 5 though, so, simply counting the number of multiples of 5 is sufficient.

1 public int count(int num){
2     int count = 0;
3     if(num < 0) return -1;
4     for(int i = 5; num /i > 0; i *= 5)
5         count += num / i;
6     return count;
7 }

17.4 Write a method which finds the maximum of two numbers. You should not use if-else or any other comparison operator.

 1 public int flip(int bit){
 2     return 1 ^ bit;
 3 }
 4 public int sign(int a){
 5     return flip((a >> 31) & 0x1);
 6 }
 7 public int getMax(int a, int b){
 8     int c = a - b;
 9     int sa = sign(a); //if a >= 0 : 1 other : 0
10     int sb = sign(b); //if b >= 1 : 1 other : 0
11     int sc = sign(c); //depends on whether a - b overflows, like a = INT_MAX, b < 0
12     int use_sign_a = sa ^ sb;
13     int use_sign_c = flip(sa ^ sb);
14     int k = use_sign_a * sa + use_sign_c * sc;
15     int q = flip(k);
16     return a * k + b * q;
17 }

17.9 Design a method to find the frequency of occurrences of any given word in a book.

The first question that you should ask is if you will be doing this operation once or repeatedly.

Solution: Single Query

go through the book, word by word, count the number of times that words appears. O(n)

Solution: Repetitive Queries

do pre-processing on the book! create a hash table which maps from a word to its frequency.

 1 Hashtable<String, Integer> setupDic(String[] book){
 2     Hashtable<String, Integer> table = new Hashtable<String, Integer>();
 3     for(String word : book){
 4         word = word.toLowerCase();
 5         if(word.trim() != ""){
 6             if(!table.containsKey(word)) table.put(word, 0);
 7             table.put(word, table.get(word) + 1);
 8         }
 9     }
10     return table;
11 }
12 int getFrequency(Hashtable<String, Integer> table, String word){
13     if(table == null || word == null) return -1;
14     word = word.toLowerCase();
15     if(table.containsKey(word)) return table.get(word);
16     return 0;
17 }

17.11 Implement a method rand7() given rand5(). Given a method that generates a random number between 0 and 4, write a method that generates a random number between 0 and 6.

Nondeterministic Number of Calls

1 public int rand7(){
2     while(true){
3         int num = 5 * rand5() + rand5();
4         if(num < 21) return num % 7;
5     }
6 }