## Number Of Divisors In A Range

### October 28, 2014

We have today an interview question that was posted to the internet by a candidate who didn’t get the job, and wondered what he had done wrong. I’ll paraphrase his question:

The interview question was to find the number of integers between

xandythat are divisible byn; you may assume thatx,yandnare all positive and thatx<y. I know the simple way to solve this is to loop over the range fromxtoy, like this:

`for(int i=x;i<=y;i++) if(i%n ==0) counter++;`

but that is very slow when the range is large, for instance

x= 0 andy= 3000000000.There must be some method that lets me reduce the number of iterations and optimize the code. Can someone please help me with that?

Your task is to help the candidate get the job by proposing a better algorithm to solve the problem. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Three Farmers

### October 24, 2014

Today’s exercise is a math puzzle from Terence Tao:

Three farmers were selling chickens at the local market. One farmer had 10 chickens to sell, another had 16 chickens to sell, and the last had 26 chickens to sell. In order not to compete with each other, they agreed to all sell their chickens at the same price. But by lunchtime, they decided that sales were not going so well, and they all decided to lower their prices to the same lower price point. By the end of the day, they had sold all their chickens. It turned out that they all collected the same amount of money, $35, from the day’s chicken sales. What was the price of the chickens before lunchtime and after lunchtime?

Your task is to calculate the price of chickens before and after lunch. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Two-Base Palindromes

### October 21, 2014

I wanted to do this exercise as a follow-up to the earlier exercise on generating palindromes, but didn’t get around to it until now.

Your task is to write a program that generates a list of numbers that are palindromes in base 10 and base 8; for instance 1496941_{10} = 5553555_{8}. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Blackjack

### October 17, 2014

Blackjack is a casino game of chance, played by a player and a dealer. Both player and dealer are initially dealt two cards from a standard 52-card deck. If the player’s initial hand consists of an ace and a ten or face card, the player wins, unless the dealer also has an ace and a ten or face card, in which case the game is a tie. Otherwise, the player draws cards until he decides to stop; if at any time the sum of the pips on the cards (aces count either 1 or 11, face cards count 10) exceeds 21, the player is busted, and loses. Once the player is finished, the dealer draws cards until he has 17 or more pips, or goes bust, at which time the game ends. If neither has gone bust, the hand with the most pips wins. There are many variant rules, but we’ll keep things simple with the rules described above.

Your task is to simulate Blackjack and determine the winning percentage for the player. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Spiral Wrapping

### October 14, 2014

Today’s exercise appears regularly on lists of interview questions. We’ve done something similar in the past, but since it’s so common we’ll do it again.

Given a matrix, print a list of elements of the matrix. Start in the top-right corner of the matrix, move left across the top row, then down the left column, then across the bottom row, then up the right column to the element below the top row, then left, then down, then right, and so on, collecting the elements of the matrix as it goes. For instance, with this matrix

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20the elements are collected in order 4, 3, 2, 1, 5, 9, 13, 17, 18, 19, 20, 16, 12, 8, 7, 6, 10, 14, 15, 11.

Your task is to write a program to unwrap the elements of a matrix in the indicated spiral. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Formatting Text, Again

### October 10, 2014

Today’s exercise is a continuation of the previous exercise, which filled text to the maximum column width. Today’s exercise is to add justification to the previous exercise, so that extra space at the end of line of text is distributed to the spaces between the words on the line, making each line end at the right margin.

Your task is to write a program that fills and justifies text. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Text Formatting

### October 7, 2014

Text formatting is a huge topic. Today’s exercise looks at a simple text formatter. Input to the formatter is a file of ascii text; the input is free-form, except that paragraphs are marked by blank lines (two successive newline). The formatter copies the file to its output, moving text from one line to the previous line to fill each line as much as possible. It is possible to specify the width of a line, but if none is given the width defaults to sixty characters.

Your task is to write a simple text formatter. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Magic 1089

### October 3, 2014

I’ve been very busy at work this week, so I only have time for a simple exercise today.

This is a simple puzzle in arithmetic. Take any three-digit number with digits in descending order; for instance, 532 is acceptable, but 481 is not. Reverse the digits of the original number, and subtract the reversal from the original. Then reverse that difference, and add the reversal of the difference to the difference. Write the result as output.

For instance, start with the number 532. Its reversal is 235, and the difference is 532 – 235 = 297. Reversing the difference gives 792, and 297 + 792 = 1089, which is the result.

Your task is to write a program that makes this calculation, and try it on several different starting numbers; you might enjoy working out the arithmetic behind the results that you see. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Thue-Morse Sequence

### September 30, 2014

Mathematicians are strange people. As an example, I offer the Thue-Morse sequence, which is a binary sequence of 0’s and 1’s that never repeats, obtained by starting with a single 0 and successively appending the binary complement of the sequence. Thus, term 0 of the sequence is (0), term 1 of the sequence is (0 1), term 2 of the sequence is (0 1 1 0), term 3 of the sequence is (0 1 1 0 1 0 0 1), term 4 of the sequence is (0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0), and so on; to calculate term 3 from term 2, we started with term 2 (0 1 1 0), complemented each element of the term (1 0 0 1), then appended the two (0 1 1 0 1 0 0 1). That looks useless to me, but mathematicians have been excited by it since 1851, hence my conclusion that mathematicians are strange people.

Your task is to write a program that generates the *n*term of the Thue-Morse sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Blum’s Mental Hash

### September 26, 2014

It is generally accepted wisdom that people should use different passwords for each of their online accounts. Unfortunately, few people do that because of the difficulty of remembering so many passwords.

Manuel Blum — he’s the guy in the middle of the Blum Blum Shub sandwich — suggests an algorithm that hashes a web site name into a password. Further, his algorithm is cryptographically secure, so no one else can determine your password, and can be worked mentally, without a computer or even pencil and paper.

Blum’s algorithm works in two steps. A function *f* maps letters to digits, and a permutation *g* transposes the digits. The two, taken together, form your personal key, and so must be kept secret.

The first step maps letters to digits; since there are more letters than digits, some of the digits are used more than once. If, for instance, *f*(*a*) = 8, *f*(*b*) = 3, and *f*(*c*) = 7, then the first step would map the input “abc” to the digits [8, 3, 7].

The second step uses the permutation *g* to calculate the output. Begin with the first and last digits, adding them mod 10; in the example, (8 + 7) % 10 = 5. If the permutation *g* = 0298736514, then the next digit after 5 is 1, so the first output digit is 1.

After that, each remaining input digit is the basis of an output digit. Calculate the sum of the next input digit and the previous output digit, mod 10, and take the next digit of the permutation, repeating for each remaining input digit. In the example, the second input digit and the first output digit are summed mod 10, (3 + 1) % 10 = 4, and the next digit in the permutation is 0 (wrapping around), so the second output digit is 0. In the same way, the third output digit takes the third input digit and the second output digit, sums them mod 10, and computes the permutation, so (7 + 0) % 10 = 7, which permutes to 3. So the final password produced from an input of “abc” is “103”.

Your task today is to implement Manuel Blum’s mental hashing algorithm for mapping a web site name to a password. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.