## Floor And Ceiling In An Array

### November 21, 2017

We looked at variants of binary search in two recent exercises. Today we look at a third variant.

Your task is to write a variant of binary search in a sorted array without duplicates that returns the index of the two elements immediately below and above a target; if the target is in the array, both return values should point to the target value. 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.

## Casting Out Nines

### November 17, 2017

It doesn’t seem to be taught any more (neither of my daughters have ever heard of it), but casting out nines is a useful computational trick for verifying manual arithmetic calculations. Consider the sum below:

3074 6017 13814 1810 27 3611 ----- 28353

The sum of the digits of 3074 is 14, and the sum of the digits of 14 is 5, so the result of casting out nines from 3074 is 5. The sum of the digits of 6017 is 14, and the sum of the digits of 14 is 5, so the result of casting out nines from 6107 is 5. The number 13814 includes digits 1 and 8, which sum to 9, so we can ignore them and sum the digits 3, 1 and 4, so the result of casting out nines from 13814 is 8. Likewise, the 1 and 8 of 1810 sum to 9, so we ignore them, and the result of casting nines out of 1810 is 1. The digits of the 27 sum to 9, which we cast out, so the result of casting nines out of 27 is 0. Finally, we can cast out the 3 and 6 from 3611, so the result of casting nines out of 3611 is 2. Now the nines results of the six numbers are 5, 5, 8, 1, 0 and 2, and again we cast out the 8 and 1, leaving 12. The sum of the digits of 12 is 3, which is the final result of casting out nines from the addends.

The sum of the digits of 28353 is 21, and the sum of the digits of 21 is 3, so the result of casting nines out of 28353 is 3. Since the addends and the sum have the same result when casting out nines, it is plausible that the sum is correct. If the process of casting out nines yielded different results from the addends and the sum, we could be sure that the sum was incorrect.

Although that formulation sounds complicated, in practice this goes faster than you can think. Consider 28353. The first two digits sum to 10, so cast out a nine and count 1. Then add 3, giving a running nine-sum of 4, and add 5, giving a running nine-sum of 9, which can be cast out. The only remaining digit is 3, which is the result of casting out nines from the sum.

Casting out nines from the addends is even easier, because there are more ways to make nine. From the first two addends, cast out the 3 and 6, then cast out the 7, 4, and 7, leaving 1. Adding the third number gives 0; cast out the 1 and 8 immediately, leaving the 1 carried from the first two numbers, plus 3, 1 and 4, which sums to 9, which is equivalent to 0. Cast out 1 and 8 from the fourth number, leaving 1, cast out the fifth number entirely, and cast out 3 and 6 from the sixth number, leaving the carry of 1 plus the two 1s at the end of the sixth number, for a total of 3.

With a little bit of practice, this becomes ridiculously fast. Your friends will be amazed when you quickly tell them their sum is wrong; they will also hate you.

Mathematically, casting out nines is the same as addition modulo 9. MathWorld gives a good explanation. The process of casting out nines works for multiplication and exponentiation as well as addition.

Your task is to write a program to cast out nines; avoid the temptation to simply take the remainder on division by 9 and do the actual work of summing the digits and casting out nines. 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.

## Odd Appearances

### November 14, 2017

Today’s exercise is the kind of interview question that I don’t like. If you know the trick, you look like a genius, and if you don’t know the trick, you don’t get the job:

In an unsorted array of integers, find the one integer that appears an odd number of times. You may use O(

n) time and O(1) space. For instance, in the array [4, 3, 6, 2, 6, 4, 2, 3, 4, 3, 3], the number 2 appears 2 times, the number 3 appears 4 times, the number 4 appears 3 times, and the number 6 appears 2 times, so the correct answer is 4.

Your task is to write a program to find the integer that appears an odd number of times. 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.

## Ternary Search

### November 10, 2017

We looked at binary search in the previous exercise. Today we look at ternary search. Instead of one `mid`

at the middle of the array, ternary search has two `mid`

s a third of the way from each end; two-thirds of the array is discarded at each recursive step.

Your task is to write a program that performs ternary search. 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.

## Binary Search With Duplicates

### November 7, 2017

Most implementations of binary search assume that the target array has no duplicates. But sometimes there are duplicates, and in that case you want to find the *first* occurrence of an item, not just any one of several occurrences. For instance, in the array [1,2,2,3,4,4,4,4,6,6,6,6,6,6,7] the first occurrence of 4 is at element 4 (counting from 0), the first occurrence of 6 is at element 8, and 5 does not appear in the array.

Your task is to write a binary search that finds the first occurrance of a set of duplicate items in a sorted array. 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.

## GCD By Factoring

### November 3, 2017

Regular readers of this blog know that Euclid’s algorithm, dating to 300 B.C., is the standard algorithm for computing the greatest common divisor of two numbers. But middle school teachers have their students calculate the greatest common divisor by factoring the two numbers and taking the product of the prime factors they have in common, being careful to count multiplicities correctly.

Your task is to write a program that calculates greatest common divisors by factoring. 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.

## Inversions

### October 31, 2017

In an array *A*, the term *inversions* refers to the number of items that are out of order; each *i* < *j* for which *A*[*j*] < *A*[*i*] counts as a single inversion. For instance, the array [1 4 3 2 5] has three inversions: (4,3), (4,2) and (3,2). Inversions are a measure of the disorder of an array: an ordered array has no inversions and a reversed array has the maximum *n*(*n*−1)/2 number of inversions.

Your task is to write programs that count the number of inversions in an array and make an enumeration of them. 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.

## The Prime Ant

### October 27, 2017

The *prime ant* (A293689) is an obstinate animal that navigates the integers and divides them until there are only primes left, according to the following procedure:

An infinite array *A* is initialized to contain all the integers greater than 1: [2, 3, 4, 5, 6, …].

Let *p* be the position of the ant on the array. Initially *p* = 0, so the ant is at *A*[0] = 2.

At each turn, the ant moves as follows:

- If
*A*[*p*] is prime, move the ant one position forward, so*p*←*p*+ 1. - Otherwise (if
*A*[*p*] is composite), let*q*be its smallest divisor greater than 1. Replace*A*[*p*] with*A*[*p*] ÷*q*. Replace*A*[*p*−1] with*A*[*p*−1] +*q*. Move the ant one position backward, so*p*←*p*− 1.

Your task is to write a program that computes the position of the prime ant after *n* turns; for instance, after 47 turns the prime ant will be at *p* = 9. 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.

## Arithmetic Progressions

### October 24, 2017

I continue today working through my backlog of homework problems:

Given an array of at least three distinct positive integers sorted in ascending order, find all triples of array elements that form an arithmetic progression, so that the difference between the first and second elements is the same as the difference between the second and third elements. For instance, in the array (1 2 3 4 6 7 9) there are five triplets in arithmetic progressions: (1 2 3), (2 3 4), (2 4 6), (1 4 7), and 3 6 9).

Your task is to write a program that finds all the arithmetic progressions in an array; for extra credit, do the same thing for geometric progressions, where the ratios of the first to second element and the second to third elements are the same. 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.

## Partial Products Of An Array

### October 20, 2017

We have another homework problem today:

Replace each element of an array with the product of every other element of the array, without using the division operator. For instance, given array (5 3 4 2 6 8), the desired output is (1152 1920 1440 2880 960 720).

Your task is to write a program to replace each element of an array with the product of every other element of the array, without performing division. 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.