Maths, Pattern and Recursion
01 Even or Odd
Solution and explanation
- Use the remainder operator.
- An integer is even when division by 2 leaves remainder 0; otherwise it is odd.
- Time O(1), space O(1).
static boolean isEven(int n) {
return n % 2 == 0;
}
System.out.println(isEven(42)); // trueTest positive, negative and zero values. Then return the text EVEN or ODD.
Quick check
Which statement is correct?
02 Sum of Natural Numbers
Solution and explanation
- The arithmetic-series formula computes 1 through n without a loop.
- Use long before multiplication to reduce integer overflow risk.
- Time O(1), space O(1).
static long sum(long n) {
if (n < 0) throw new IllegalArgumentException();
return n * (n + 1) / 2;
}Compare the formula with a loop for n values from 0 to 100.
Quick check
Which statement is correct?
03 Closest Number Divisible by M
Solution and explanation
- Compute the lower multiple using integer division and compare it with the next multiple.
- Define how ties and negative inputs should behave before coding.
static int closest(int n, int m) {
if (m == 0) throw new IllegalArgumentException();
int q = n / m;
int a = m * q;
int b = n * m > 0 ? m * (q + 1) : m * (q - 1);
return Math.abs(n - a) < Math.abs(n - b) ? a : b;
}Test 13 with divisor 4, a tie case, and negative values.
Quick check
Which statement is correct?
04 Floyd’s Triangle
Solution and explanation
- Floyd’s triangle prints consecutive integers across rows of increasing length.
- A running counter avoids recomputing each value.
- Time O(rows²).
static void floyd(int rows) {
int value = 1;
for (int row = 1; row <= rows; row++) {
for (int col = 1; col <= row; col++)
System.out.print(value++ + " ");
System.out.println();
}
}Print five rows, then modify the program to collect rows in a list for testing.
Quick check
Which statement is correct?
05 Print 1 to N Using Recursion
Solution and explanation
- The base case stops at zero.
- Recursive calls first move toward the base case, then printing during stack unwinding produces ascending order.
- Time O(n), stack O(n).
static void printOneToN(int n) {
if (n <= 0) return;
printOneToN(n - 1);
System.out.print(n + " ");
}Move the print statement before the recursive call and explain why the order reverses.
Quick check
Which statement is correct?
06 Factorial
Solution and explanation
- Factorial follows n! = n × (n−1)! with 0! = 1.
- Standard numeric types overflow quickly, so BigInteger is appropriate for larger n.
static BigInteger factorial(int n) {
if (n < 0) throw new IllegalArgumentException();
if (n <= 1) return BigInteger.ONE;
return BigInteger.valueOf(n).multiply(factorial(n - 1));
}Implement iterative and recursive versions and compare stack usage.
Quick check
Which statement is correct?
07 Greatest Common Divisor
Solution and explanation
- Euclid’s algorithm repeatedly replaces (a,b) with (b,a mod b).
- It finishes when b becomes zero.
- Time O(log min(a,b)).
static int gcd(int a, int b) {
a = Math.abs(a); b = Math.abs(b);
while (b != 0) {
int remainder = a % b;
a = b; b = remainder;
}
return a;
}Use gcd to implement lcm safely and test gcd(48,18).
Quick check
Which statement is correct?
08 Power with Fast Exponentiation
Solution and explanation
- Exponentiation by squaring halves the exponent each step.
- Even exponents square the half result; odd exponents multiply by the base once more.
- Time O(log exponent).
static long power(long base, int exp) {
if (exp < 0) throw new IllegalArgumentException();
if (exp == 0) return 1;
long half = power(base, exp / 2);
long result = half * half;
return exp % 2 == 0 ? result : result * base;
}Trace power(2,10), then discuss overflow and modular exponentiation.
Quick check
Which statement is correct?
09 Prime Testing
Solution and explanation
- A composite number must have a factor no greater than its square root.
- Check 2 separately, then test odd divisors while d ≤ n/d to avoid overflow.
static boolean isPrime(int n) {
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
for (int d = 3; d <= n / d; d += 2)
if (n % d == 0) return false;
return true;
}Test 1, 2, 3, 4, 97 and a large composite number.
Quick check
Which statement is correct?
10 Armstrong Number
Solution and explanation
- For a k-digit number, sum each digit raised to k and compare the result with the original number.
- Example: 153 = 1³+5³+3³.
static boolean isArmstrong(int n) {
if (n < 0) return false;
int digits = String.valueOf(n).length();
int value = n; long total = 0;
do {
int digit = value % 10;
total += Math.round(Math.pow(digit, digits));
value /= 10;
} while (value != 0);
return total == n;
}Test 0, 153, 370, 9474 and 100. Replace Math.pow with an integer-power helper.
Quick check
Which statement is correct?
Spring Quiz: Lessons 1 – 10
Test what you have learned before continuing to the next learning block.
Which statement is correct?
Which statement is correct?
Which statement is correct?
Which statement is correct?
Which statement is correct?
Which statement is correct?
Which statement is correct?
Which statement is correct?
Which statement is correct?
Which statement is correct?
11 Tower of Hanoi
Solution and explanation
- Move n−1 disks to the helper peg, move the largest disk to the destination, then move n−1 disks onto it.
- Moves are 2ⁿ−1; time O(2ⁿ), stack O(n).
static void hanoi(int n, char from, char helper, char to) {
if (n == 0) return;
hanoi(n - 1, from, to, helper);
System.out.println(from + " -> " + to);
hanoi(n - 1, helper, from, to);
}Print moves for three disks and verify exactly seven moves occur.
Quick check
Which statement is correct?
12 Josephus Problem
Solution and explanation
With zero-based indexing, the survivor satisfies J(1)=0 and J(n)=(J(n−1)+k) mod n. Add one for a one-based answer. Time O(n), space O(1) iteratively.static int josephus(int n, int k) {
if (n <= 0 || k <= 0) throw new IllegalArgumentException();
int survivor = 0;
for (int size = 2; size <= n; size++)
survivor = (survivor + k) % size;
return survivor + 1;
}Trace n=7, k=3 manually and compare with the algorithm.
Quick check
Which statement is correct?