Week 1: Exercises

1. Not Divisible by 3, 5, 7

Write a program that prints the sum of all integers in the range 0 ≤ i ≤ 1,000,000 such that i is not divisible by any of the numbers {3, 5, 7}.

2. Smallest Multiple

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? Either write a program to determine the answer, or compute it mathematically.

3. Palindrome Test

Write a program that reads a string from the console and prints "palindrome" if it is a palindrome, otherwise "not"'.

4. Capitalized Words

Write a program that reads a string and writes it back out, capitalizing the first letter of every word.

5. Hailstone Sequence

A hailstone sequence of integers H_i starting from any integer H₁ is defined as follows: If H_i is even, then H_{i + 1} = H_i / 2; otherwise H_{i + 1} = 3 H_i + 1. For example, the sequence starting from H₁ = 10 is 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ...

Write a program that determines and prints the first value k for which the hailstone sequence starting at k rises above 1,000,000,000.

6. S Begins With T

Write a program that reads two strings S and T, each on its own line. The program should print "true" if S starts with T, "false" otherwise.

7. Exponentiation

Write a program that reads an integer A and an integer B ≥ 0 and prints the value of A^B. Implement exponentiation using repeated multiplication.

8. Decimal to Binary

Write a program that reads a decimal integer and prints it out in base 2, i.e. binary.

9. Making Change

Read a price in Czech crowns. Print out a combination of 20-Kč, 10-Kč, 5-Kč and 1-Kč coins that add up to the price, using the smallest possible number of coins.

Enter price: 67
20 Kc: 3
10 Kc: 0
5 Kc: 1
1 Kc: 2

10. Printing with Commas

Write a program that reads an integer which may be arbitrarily large, and writes the integer with embedded commas.

Input:

28470562348756298345

Output:

28,470,562,348,756,298,345

11. Roll of the Dice

Write a program that reads an integer N and simulates rolling N 6-sided dice until all dice have the value 1. The program should print the number of rolls that were required. (On average, what number will the program print for a given N?)

12. Number of Words

Write a method that counts the number of words in standard input. Here, a word is any contiguous sequence of non-whitespace characters.

13. Rotate a Matrix

Write a static method that takes N x N matrix of integers and rotates it 90 degrees to the right.

Input:

2 4 6 8
8 6 4 2
1 3 7 9
9 7 3 1

Output:

9 1 8 2
7 3 6 4
3 7 4 6
1 9 2 8

14. All Ints

Write a program that computes and prints the sum of every possible value of an int. Can you determine what value it will print even before you run it?

15. Counting Sundays

(Project Euler, problem 19)

January 1, 1900 was a Monday.

Write a program that determines how many Sundays fell on the first of the month during the 20^th century (January 1, 1901 – December 31, 2000).

16. Integer Square Root

Write a function

  function intSqrt(n: integer): integer;

that finds the integer square root of n, i.e. the non-negative integer i such that i * i = n. If no such integer exists, return -1. Do not call any library functions. Your function must run in time O(log N) in the worst case.

17. Sorting Two Values

Write a method sort(int[] a) that sorts an array of integers which is guaranteed to contain at most two distinct values. How efficient is your method?

18. Largest Product in a Series

Solve Project Euler's problem 8, assuming that the input number is in a file called 'number'.

19. Largest Product in a Grid

Solve Project Euler's problem 11, assuming that the input number is in a file called 'numbers'.

20. Large Sum

Solve Project Euler's problem 13, assuming that the input numbers are in a file called 'numbers'.

21. Power Digit Sum

(Project Euler, problem 16)

Write a program that determines the sum of the digits of the number 2¹⁰⁰⁰.

22. Number Spiral Diagonals

Solve Project Euler's problem 28.