🧮 Day 9: Math Problems Challenge

Solve 10 Essential Math Problems for Coding Interviews

10
Total Problems
0
Solved
⭐⭐⭐
Difficulty Mix
Problem 1: Optimized Prime Check
Easy
Write a function to check if a given number is prime. Your solution should be optimized for time complexity.

Examples:

Input: 17 → Output: True
Input: 25 → Output: False
Input: 2 → Output: True
Input: 1 → Output: False
Constraints:
  • 1 ≤ n ≤ 10^6
  • Handle edge cases for n ≤ 1

Hints:

Only check divisors up to √n
Handle 2 as a special case, then check only odd numbers
Return False immediately for even numbers > 2
Expected Time
O(√n)
Expected Space
O(1)
Prime Numbers Math Optimization
Problem 2: Fibonacci nth Term
Easy
Calculate the nth Fibonacci number efficiently without using recursion. The sequence starts with F(0) = 0, F(1) = 1.

Examples:

Input: 10 → Output: 55
Input: 0 → Output: 0
Input: 1 → Output: 1
Input: 7 → Output: 13
Constraints:
  • 0 ≤ n ≤ 50
  • Must use O(1) space complexity
Use two variables to track the last two Fibonacci numbers
Iterate from 2 to n, updating the variables
Handle base cases n=0 and n=1 separately
Expected Time
O(n)
Expected Space
O(1)
Fibonacci Dynamic Programming Iterative
Problem 3: Greatest Common Divisor
Easy
Find the Greatest Common Divisor (GCD) of two positive integers using the Euclidean algorithm.

Examples:

Input: 48, 18 → Output: 6
Input: 17, 13 → Output: 1
Input: 100, 25 → Output: 25
Constraints:
  • 1 ≤ a, b ≤ 10^9
  • Both numbers are positive integers
Use the Euclidean algorithm: gcd(a,b) = gcd(b, a%b)
Continue until one number becomes 0
Can be implemented iteratively or recursively
Expected Time
O(log min(a,b))
Expected Space
O(1)
GCD Euclidean Algorithm Number Theory
Problem 4: Trailing Zeros in Factorial
Medium
Given an integer n, count the number of trailing zeros in n! (factorial of n).

Examples:

Input: 5 → Output: 1 (5! = 120)
Input: 10 → Output: 2 (10! = 3628800)
Input: 25 → Output: 6
Input: 100 → Output: 24
Constraints:
  • 0 ≤ n ≤ 10^4
  • Don't calculate the factorial directly
Trailing zeros come from factors of 10 = 2 × 5
Count factors of 5 (there are always more factors of 2)
Don't forget about multiples of 25, 125, etc.
Expected Time
O(log n)
Expected Space
O(1)
Factorial Math Number Theory
Problem 5: Fast Exponentiation
Medium
Implement pow(x, n) which calculates x raised to the power n. Handle negative exponents.

Examples:

Input: 2, 10 → Output: 1024
Input: 2.1, 3 → Output: 9.261
Input: 2, -2 → Output: 0.25
Input: 5, 0 → Output: 1
Constraints:
  • -100 ≤ x ≤ 100
  • -2^31 ≤ n ≤ 2^31-1
  • Optimize for time complexity
Use binary exponentiation for efficiency
If n is even: x^n = (x^(n/2))^2
If n is odd: x^n = x * x^(n-1)
Handle negative exponents: x^(-n) = 1/(x^n)
Expected Time
O(log n)
Expected Space
O(1)
Exponentiation Binary Search Math
Problem 6: Perfect Number Check
Medium
A perfect number is a positive integer that is equal to the sum of its proper positive divisors. Determine if a given number is perfect.

Examples:

Input: 28 → Output: True (1+2+4+7+14 = 28)
Input: 6 → Output: True (1+2+3 = 6)
Input: 12 → Output: False
Input: 1 → Output: False
Constraints:
  • 1 ≤ num ≤ 10^8
  • Optimize to avoid timeout
Find all proper divisors efficiently
Only check up to √num for divisors
Add both i and num/i when i divides num
Expected Time
O(√n)
Expected Space
O(1)
Perfect Numbers Divisors Math
Problem 7: Reverse Integer
Medium
Reverse the digits of a 32-bit signed integer. If reversing causes overflow, return 0.

Examples:

Input: 123 → Output: 321
Input: -123 → Output: -321
Input: 120 → Output: 21
Input: 1534236469 → Output: 0 (overflow)
Constraints:
  • -2^31 ≤ x ≤ 2^31 - 1
  • Return 0 if reversed integer overflows
Extract digits using modulo and integer division
Handle negative numbers separately
Check for overflow before building result
Expected Time
O(log n)
Expected Space
O(1)
Digit Manipulation Integer Overflow Math
Problem 8: Count Primes up to N
Medium
Count the number of prime numbers less than a non-negative integer n using the Sieve of Eratosthenes.

Examples:

Input: 10 → Output: 4 (2, 3, 5, 7)
Input: 0 → Output: 0
Input: 1 → Output: 0
Input: 20 → Output: 8
Constraints:
  • 0 ≤ n ≤ 5 * 10^6
  • Must be efficient for large inputs
Use Sieve of Eratosthenes algorithm
Mark multiples starting from i^2, not 2*i
Only iterate up to √n for marking
Expected Time
O(n log log n)
Expected Space
O(n)
Sieve of Eratosthenes Prime Numbers Array
Problem 9: LCM of Multiple Numbers
Hard
Find the Least Common Multiple (LCM) of an array of positive integers. Optimize to avoid integer overflow.

Examples:

Input: [4, 6, 8] → Output: 24
Input: [12, 18] → Output: 36
Input: [2, 3, 5] → Output: 30
Input: [1] → Output: 1
Constraints:
  • 1 ≤ arr.length ≤ 1000
  • 1 ≤ arr[i] ≤ 10^6
  • Handle potential overflow
Use the relationship: LCM(a,b) = (a*b)/GCD(a,b)
Calculate LCM iteratively: LCM(a,b,c) = LCM(LCM(a,b), c)
Avoid overflow: divide before multiplying
Expected Time
O(n * log(max))
Expected Space
O(1)
LCM GCD Array Overflow
Problem 10: Armstrong Number in Range
Hard
Find all Armstrong numbers in a given range [start, end]. An Armstrong number equals the sum of its digits raised to the power of the number of digits.

Examples:

Input: 1, 1000 → Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 371, 407]
Input: 100, 200 → Output: [153]
Input: 1, 10 → Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Constraints:
  • 1 ≤ start ≤ end ≤ 10^6
  • Return results in ascending order
  • Optimize for large ranges
153 = 1³ + 5³ + 3³ (3 digits, power 3)
Pre-calculate powers for efficiency
Group numbers by digit count for optimization
Expected Time
O((end-start) * log end)
Expected Space
O(result size)
Armstrong Numbers Digit Manipulation Range Query Math

🎯 Challenge Summary

Congratulations! You've completed all 10 math problems. Here's what you've mastered:

Next Steps: Practice these problems on coding platforms like LeetCode, HackerRank, or CodeChef to reinforce your understanding!