An Odd Way To Square
February 26, 2013
I’m not sure where this comes from; it could be an interview question, or some kind of programming puzzle:
Write a function that takes a positive integer n and returns n-squared. You may use addition and subtraction but not multiplication or exponentiation.
Your task is to write the squaring function 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.
Floupia
February 22, 2013
[ Today’s exercise was contributed by Tom Rusting, who worked as a programmer until the mid 70’s. Being retired, he has now taken up programming again as a hobby. Suggestions for exercises are always welcome, or you may wish to contribute your own exercise; feel free to contact me if you are interested.
Floup is an island-country in the South Pacific with a currency known as the floupia; coins are denominated in units of 1, 3, 7, 31 and 153 floupias. Merchants and customers engage in a curious transaction when it comes time to pay the bill; they exchange the smallest number of coins necessary to complete the payment. For instance, to pay a bill of 17 floupia, a customer could pay three 7-floupia coins and receive single 1-floupia and 3-floupia coins in exchange, a total of five coins, but it is more efficient for the customer to pay a single 31-floupia coin and receive two 7-floupia coins in exchange.
Your task is to write a program that determines the most efficient set of coins needed to make a payment, generalized for any set of coins, not just the set 1, 3, 7, 31 and 153 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.
NPR Sunday Puzzle
February 19, 2013
[ Today is the fourth anniversary of Programming Praxis, which published five exercises on February 19, 2009. I remember getting 6 hits that day, all of them from one friend that I told about the blog. I get a few more hits now. Many thanks to all of my readers, whose comments and emails inspire me to continue. — Phil ]
We haven’t done a word puzzle for a while. Here is one from the NPR Sunday Puzzle:
Think of two familiar, unhyphenated, eight-letter words that contain the letters A, B, C, D, E and F, plus two others, in any order. What words are these?
Your task is to write a program to find the two words. 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.
Facebook Hacker Cup 2013, Round 1, Problem 1
February 15, 2013
Round 1 of the Facebook Hacker Cup 2013 is now complete. In today’s exercise we look at Problem 1:
CARD GAME (20 points)
John is playing a game with his friends. The game’s rules are as follows: There is deck of N cards from which each person is dealt a hand of K cards. Each card has an integer value representing its strength. A hand’s strength is determined by the value of the highest card in the hand. The person with the strongest hand wins the round. Bets are placed before each player reveals the strength of their hand.
John needs your help to decide when to bet. He decides he wants to bet when the strength of his hand is higher than the average hand strength. Hence John wants to calculate the average strength of ALL possible sets of hands. John is very good at division, but he needs your help in calculating the sum of the strengths of all possible hands.
PROBLEM
You are given an array a with N ≤ 10000 different integer numbers and a number, K, where 1 ≤ K ≤ N. For all possible subsets of a of size K find the sum of their maximal elements modulo 1000000007.
INPUT
The first line contains the number of test cases T, where 1 ≤ T ≤ 25
Each case begins with a line containing integers N and K. The next line contains N space-separated numbers 0 ≤ a [i] ≤ 2000000000, which describe the array a.
OUTPUT
For test case i, numbered from 1 to T, output "Case #i: ", followed by a single integer, the sum of maximal elements for all subsets of size K modulo 1000000007.
EXAMPLE
For a = [3, 6, 2, 8] and N = 4 and K = 3, the maximal numbers among all triples are 6, 8, 8, 8 and the sum is 30.
EXAMPLE INPUT
5
4 3
3 6 2 8
5 2
10 20 30 40 50
6 4
0 1 2 3 5 8
2 2
1069 1122
10 5
10386 10257 10432 10087 10381 10035 10167 10206 10347 10088EXAMPLE OUTPUT
Case #1: 30
Case #2: 400
Case #3: 103
Case #4: 1122
Case #5: 2621483
Your task is to write a program that solves the Facebook problem given 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.
Binary Search Tree: In-Order Predecessor And Successor
February 12, 2013
We have seen several flavors of binary search trees, including classic bsts, treaps, red/black trees, and avl trees. For all of them we provided a lookup function that returned a requested key/value pair. In today’s exercise we write functions that return the predecessor and successor of a requested key, allowing a program to walk the tree in order. There are two common variants of these functions, one using parent pointers and one without; our exercise will use the variant without parent pointers, which is generally more useful.
We give the basic logic for the successor function; the predecessor function is similar, but reversed. A recursive function descends the tree searching for the requested key, keeping track of the current tree as the possible successor every time if follows the left sub-tree. If it finds the key, its successor is the minimum element of the right sub-tree, found by chasing left sub-trees until reaching a null node. If the search reaches a null node and hence fails to find the key, the next largest key in the tree is the successor, found in the possible successor that was saved at each recursive call.
Your task is to write predecessor and successor functions for binary search trees. 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 Biggest Prime
February 8, 2013
It has been widely reported that a new “biggest prime” was found two weeks ago. The prime, which has 17,425,170 digits, is:
257,885,161 − 1
Your task is to write a program that displays all seventeen million digits of the biggest prime. 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 147 Puzzle
February 5, 2013
Today’s exercise comes to us from the world of recreational mathematics:
Find all possible solutions to the equation 1/a + 1/b + 1/c + 1/d + 1/e = 1 where all of a, b, c, d and e are positive integers.
One solution is the trivial 1/5 + 1/5 + 1/5 + 1/5 + 1/5. Another solution, based on the perfect number 1 + 2 + 4 + 7 + 14 = 28, is 1/2 + 1/4 + 1/7 + 1/14 + 1/28. The minimum distinct solution is 1/3 + 1/4 + 1/5 + 1/6 + 1/20, where all the denominators are distinct and the sum of the denominators 3 + 4 + 5 + 6 + 20 = 38 is minimum over all solutions.
Your task is to write a program to enumerate all possible solutions to the equation. 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.
Hofstadter’s Sequence
February 1, 2013
On page 73 of his book Gödel, Escher, Bach: An Eternal Golden Braid, Douglas Hofstadter asks you to think about the following sequence:
1, 3, 7, 12, 18, 26, 35, 45, 56, 69, …
Hofstadter leaves you to figure out the rule that produces the sequence, though he does give some hints in the surrounding text.
Your task is to write a program that produces the first n elements of Hofstadter’s 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.
Programming Praxis 