Consecutive Array Search

January 10, 2020

Given an array of distinct integers and a target integer, determine if two adjacent integers in the array sum to the target. Solve the problem twice, once assuming the array is unsorted and once assuming the array is sorted.

Your task is to solve the two array search problems described above. 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.

Pages: 1 2

Counting Digits

January 7, 2020

We have a simple homework question today:

Given a range of non-negative integers, count the number of 2s, 5s and 8s in the decimal representations of the digits. For instance, from 295 to 305, there are 9:

295:  2
296:  1
297:  1
298:  2
299:  1
300:  0
301:  0
302:  1
303:  0
304:  0
305:  1
Total 9

Your task is to write a program to count the 2, 5, and 8 digits in the range of integers. 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.

Pages: 1 2

Sets Without Replacement

December 18, 2019

[ Today’s exercise will be the last until next year. Expect the next exercise the week of January 6. In the meantime, enjoy the Christmas and New Year’s holidays with your families. ]

A set is an unordered collection of elements, and supports two operations: add an element, and delete an element. A set without replacement is a set where an element, once deleted from the set, cannot later be added back into the set.

Your task is to implement sets without replacement. 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.

Pages: 1 2

Pentabonacci Numbers

December 13, 2019

The sequence of pentabonacci numbers is defined as the sequence beginning 0, 1, 1, 2, 4, and continuing with each subsequent number the sum of the five previous members of the sequence. The sequence grows very quickly; the 20th member of the sequence (counting the 0 that begins the sequence as the first member) is 103519.

Your task is to write a program that calculates the first n members of the pentabonacci sequence and determine the rule that states whether the nth member of the sequence is even or odd. 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.

Pages: 1 2

Pseudoprimes To Bases 2 And 3

December 10, 2019

Regular readers know of my affinity for the Online Encyclopedia of Integer Sequences. I was browsing the other day and came across A052155, the sequence of pseudoprimes to both base2 and base3. This sequence is important because it forms the basis of a very fast primality test for numbers in the range 232 to 264, which is a very important range for some large factoring algorithms (particularly SIQS and NFS in their 2LP variants): a number n in range is prime if 2n-1 ≡ 1 (mod n), 3n-1 ≡ 1 (mod n), and n is not in a small list of known pseudoprimes to bases 2 and 3. The two modular exponentiations are reasonably quick, the lookup by binary search is even quicker, and the primality test is fully deterministic.

Your task is to calculate the pseudoprimes to bases 2 and 3 less than a million. 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.

Pages: 1 2

Muenchhausen Numbers

December 6, 2019

A radix-10 number is a Muenchhausen number if it is equal to the sum of its digits, each digit raised to the power of itself. For instance, 3435 is a Muenchhausen number because 3**3 + 4**4 + 3**3 + 5**5 = 3435. Strict Muenchhausen numbers do not permit 0 as a digit, because 0**0 is undefined. Variant Muenchhausen numbers permit 0 as a digit, with 0**0 defined as 0. Muenchhausen numbers also exist with radices other than 10.

Your task is to find all the Muenchhausen numbers in radix-10. 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.

Pages: 1 2

A Single Line Of Code

December 3, 2019

Today’s task challenges you write a useful program using only a single line of code. It is not fair to abuse the notion of a line. You can probably do more than you expect.

Your task is to write a useful program using only a single line of code. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Happy Thanksgiving

November 26, 2019

My daughter is visiting this week, so there will be no exercises. The next exercise will be on Tuesday, December 3rd. Enjoy the time with your family.

I had a lot of fun working on this problem:

Given n, find x, y and z such that x y z = n and x + y + z is minimal; for instance, given n = 1890, the correct answer is (9 14 15).

Your task is to write a program to find x, y and z. 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.

Pages: 1 2

Modified Coin Change

November 19, 2019

We solved the standard coin change problem in two previous exercises. The particular problem given here is to find the minumum number of coins that can be used to create a target amount of money, given an unlimited number of coins of various denominations, and is normally solved by a dynamic programming algorithm.

Today’s task is a variant on that problem: find the minimum number of coins that can be used to create a target amount of money, given an unlimited number of coins of denomination that are powers of 5.

Your task is to write a program to solve the modified coin change 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.

Pages: 1 2