For those who hate math, I know it doesn’t seem to be leaving you, but here’s the catch — there is no differentiation, integration, or complex quadratic equation for now. It’s just simple tasks like finding LCM, GCD, and determining whether a number is prime.
And I will tell you why you should not skip this lecture. When we want to improve the complexity of code, whether in terms of time or space, we must know which formula is consuming more compared to others, and math helps a lot with this. So just stay with me for a few questions, and then we will move on to the big ones.
/**
* Problem: Count the number of digits in a given integer n.
*
* You are given an integer `n`. Your task is to return the number of digits in the number.
* The number will not have leading zeroes except when the number is 0 itself.
*
* Example 1:
* Input: n = 4
* Output: 1
* Explanation: The number 4 has only 1 digit.
*
* Example 2:
* Input: n = 12345
* Output: 5
* Explanation: The number 12345 has 5 digits.
*
* Example 3:
* Input: n = 0
* Output: 1
* Explanation: Even though 0 is a single-digit number, it still has one digit.
*
* Approach:
* - If the number is 0, directly return 1, as it has only one digit.
* - Otherwise, initialize a counter to 0.
* - Use a loop to repeatedly divide the number by 10 to remove the last digit.
* - Increment the counter during each iteration to count the digits.
* - When the number becomes 0, return the counter as the total number of digits.
*/
class Solution {
public int countDigit(int n) {
// Special case: if the number is 0, return 1 as it has only one digit.
if (n == 0) return 1;
// Initialize the counter to keep track of the number of digits.
int count = 0;
// Use a loop to iterate through the digits of the number.
while (n > 0) {
// Remove the last digit of the number.
int lastDigit = n % 10; // This step isn't necessary for the count but helps understand the process.
// Increment the digit counter.
count++;
// Update the number by removing the last digit.
n = n / 10;
}
// Return the total count of digits.
return count;
}
}
/**
* Problem: Count the number of odd digits in a given integer n.
*
* You are given an integer `n`. Your task is to return the number of odd digits present in the number.
* The number will not have leading zeroes except when the number is 0 itself.
*
* Example 1:
* Input: n = 5
* Output: 1
* Explanation: The number 5 contains only one digit, and it is an odd digit.
*
* Example 2:
* Input: n = 25
* Output: 1
* Explanation: Among the digits in 25 (2 and 5), only 5 is odd.
*
* Example 3:
* Input: n = 0
* Output: 0
* Explanation: The number 0 has no odd digits.
*
* Example 4:
* Input: n = 12345
* Output: 3
* Explanation: The odd digits in 12345 are 1, 3, and 5, so the output is 3.
*
* Approach:
* - If the number is 0, return 0, as there are no odd digits in 0.
* - Initialize a counter to track the number of odd digits.
* - Use a loop to extract each digit of the number by repeatedly finding the remainder when divided by 10 (`n % 10`).
* - Check if the digit is odd using the condition `lastDigit % 2 != 0`.
* - If the condition is true, increment the counter.
* - Remove the last digit from the number using integer division (`n = n / 10`).
* - Continue the process until the number becomes 0, then return the count.
*/
class Solution {
public int countOddDigit(int n) {
// Special case: if the number is 0, return 0 as it has no odd digits.
if (n == 0) return 0;
// Initialize the counter to track the count of odd digits.
int count = 0;
// Use a loop to process each digit of the number.
while (n > 0) {
// Extract the last digit of the number.
int lastDigit = n % 10;
// Check if the digit is odd.
if (lastDigit % 2 != 0) {
// Increment the counter for odd digits.
count++;
}
// Remove the last digit from the number.
n = n / 10;
}
// Return the total count of odd digits.
return count;
}
}
/**
* Problem: Reverse the digits of a given integer n.
*
* You are given an integer `n`. Your task is to return the integer formed by placing the digits of `n` in reverse order.
*
* Example 1:
* Input: n = 25
* Output: 52
* Explanation: The reverse of 25 is 52.
*
* Example 2:
* Input: n = 123
* Output: 321
* Explanation: The reverse of 123 is 321.
*
* Example 3:
* Input: n = 0
* Output: 0
* Explanation: The reverse of 0 is 0 itself.
*
* Approach:
* - Initialize a variable `reverse` to store the reversed number. Start with 0.
* - Use a loop to extract each digit of the number by taking the remainder when dividing by 10 (`n % 10`).
* - Append the extracted digit to the reversed number by multiplying `reverse` by 10 and adding the digit.
* - Remove the last digit from `n` using integer division (`n = n / 10`).
* - Repeat this process until the number becomes 0.
* - Finally, return the reversed number.
*/
class Solution {
public int reverseNumber(int n) {
// Initialize the variable to store the reversed number.
int reverse = 0;
// Use a loop to process each digit of the number.
while (n > 0) {
// Extract the last digit of the number.
int lastDigit = n % 10;
// Append the digit to the reversed number.
reverse = (reverse * 10) + lastDigit;
// Remove the last digit from the original number.
n = n / 10;
}
// Return the reversed number.
return reverse;
}
}
/**
* Problem: Check if a given number is a palindrome.
*
* A palindrome number is a number that reads the same both from left to right and from right to left.
* Your task is to return `true` if the number is a palindrome, otherwise return `false`.
*
* Example 1:
* Input: n = 121
* Output: true
* Explanation:
* - When read from left to right: 121
* - When read from right to left: 121
* - Since the number reads the same in both directions, it is a palindrome.
*
* Example 2:
* Input: n = 123
* Output: false
* Explanation:
* - When read from left to right: 123
* - When read from right to left: 321
* - Since the number reads differently in both directions, it is not a palindrome.
*
* Approach:
* - First, create a copy of the input number `n` to compare with the reversed number later.
* - Initialize a variable `reverse` to store the reversed number.
* - Use a loop to reverse the digits of the number:
* - Extract the last digit of the number using `n % 10`.
* - Append the digit to the reversed number by multiplying `reverse` by 10 and adding the digit.
* - Remove the last digit of the number using integer division (`n / 10`).
* - After the loop, compare the reversed number with the original number.
* - If they are the same, return `true` (palindrome); otherwise, return `false` (not a palindrome).
*/
class Solution {
public boolean isPalindrome(int n) {
// Variable to store the reversed number.
int reverse = 0;
// Store a copy of the original number to compare later.
int copy = n;
// Reverse the digits of the number.
while (n > 0) {
// Extract the last digit of the number.
int lastDigit = n % 10;
// Append the last digit to the reversed number.
reverse = (reverse * 10) + lastDigit;
// Remove the last digit from the original number.
n = n / 10;
}
// Compare the reversed number with the original number.
if (reverse == copy) {
// If they are the same, it is a palindrome.
return true;
}
// Otherwise, it is not a palindrome.
return false;
}
}
/**
* Problem: Find the largest digit in a given integer.
*
* You are given an integer `n`. Your task is to return the largest digit in the number.
*
* Example 1:
* Input: n = 25
* Output: 5
* Explanation:
* - The digits of the number 25 are 2 and 5.
* - Among these, the largest digit is 5.
*
* Example 2:
* Input: n = 99
* Output: 9
* Explanation:
* - The digits of the number 99 are 9 and 9.
* - The largest digit is 9.
*
* Example 3:
* Input: n = 0
* Output: 0
* Explanation:
* - The only digit in 0 is 0, which is also the largest digit.
*
* Approach:
* - Initialize a variable `largestNum` to store the largest digit found so far. Start with 0.
* - Use a loop to extract each digit of the number:
* - Extract the last digit of the number using `n % 10`.
* - Compare it with `largestNum` and update `largestNum` if the extracted digit is greater.
* - Remove the last digit of the number using integer division (`n / 10`).
* - Once the loop ends, `largestNum` will contain the largest digit in the number.
* - Return `largestNum`.
*/
class Solution {
public int largestDigit(int n) {
// Initialize the variable to store the largest digit.
int largestNum = 0;
// Use a loop to process each digit of the number.
while (n > 0) {
// Extract the last digit of the number.
int lastDigit = n % 10;
// Update largestNum if the current digit is greater.
if (lastDigit > largestNum) {
largestNum = lastDigit;
}
// Remove the last digit from the original number.
n = n / 10;
}
// Return the largest digit.
return largestNum;
}
}
/**
* Problem: Check if a given number is an Armstrong number.
*
* You are given an integer `n`. Your task is to determine whether `n` is an Armstrong number.
* Return `true` if it is an Armstrong number, otherwise return `false`.
*
* Definition:
* - An Armstrong number is a number that is equal to the sum of its digits, each raised to the power of the total number of digits in the number.
*
* Formula:
* Let `n` have `d` digits, and let its digits be `a1, a2, ..., ad`.
* - Armstrong condition: n = (a1^d) + (a2^d) + ... + (ad^d)
*
* Examples:
* Example 1:
* Input: n = 153
* Output: true
* Explanation:
* - Number of digits: 3
* - Digits: 1, 5, 3
* - Calculation: 1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153
* - Since the sum is equal to the original number, it is an Armstrong number.
*
* Example 2:
* Input: n = 12
* Output: false
* Explanation:
* - Number of digits: 2
* - Digits: 1, 2
* - Calculation: 1^2 + 2^2 = 1 + 4 = 5
* - Since the sum is not equal to the original number, it is not an Armstrong number.
*
* Approach:
* 1. Find the number of digits in the number (`length`).
* 2. For each digit, calculate its value raised to the power of the total number of digits.
* 3. Sum these values.
* 4. Compare the sum to the original number. If they are equal, the number is an Armstrong number.
*/
import java.util.*;
class Solution {
public boolean isArmstrong(int n) {
// Store the original number for comparison
int copy = n;
// Step 1: Find the length (number of digits) in the number
int length = 0;
int temp = n; // Temporary variable to avoid modifying the original number
while (temp > 0) {
temp /= 10; // Remove the last digit
length++; // Increment digit count
}
// Step 2: Calculate the sum of digits raised to the power of the length
int sum = 0;
temp = n; // Reset temp to the original number
while (temp > 0) {
int lastDigit = temp % 10; // Extract the last digit
sum += Math.pow(lastDigit, length); // Add the power of the digit to the sum
temp /= 10; // Remove the last digit
}
// Step 3: Compare the calculated sum with the original number
return sum == copy;
}
}
/**
* Problem: Check if a given number is a Perfect Number.
*
* You are given an integer `n`. Your task is to determine whether `n` is a perfect number.
* Return `true` if it is a perfect number, otherwise return `false`.
*
* Definition:
* A perfect number is a positive integer that is equal to the sum of its proper divisors
* (excluding the number itself).
*
* Proper divisors are all positive divisors of a number except the number itself.
*
* Examples:
* Example 1:
* Input: n = 6
* Output: true
* Explanation:
* - Proper divisors of 6 are: 1, 2, 3.
* - Sum of proper divisors: 1 + 2 + 3 = 6.
* - Since the sum is equal to the number itself, it is a perfect number.
*
* Example 2:
* Input: n = 4
* Output: false
* Explanation:
* - Proper divisors of 4 are: 1, 2.
* - Sum of proper divisors: 1 + 2 = 3.
* - Since the sum is not equal to the number, it is not a perfect number.
*
* Approach:
* 1. Perfect numbers must be greater than 1.
* 2. Find all proper divisors of the number up to its square root.
* 3. For each divisor `i`:
* - Add `i` to the sum.
* - If `i` is not the square root of `n`, add `n / i` (the paired divisor) to the sum.
* 4. Compare the sum of the divisors with the original number.
* 5. If the sum equals the original number, it is a perfect number.
*/
class Solution {
public boolean isPerfect(int n) {
// Perfect numbers must be greater than 1
if (n <= 1) {
return false; // Numbers less than or equal to 1 are not perfect
}
// Initialize sum of divisors
int sum = 1; // 1 is a proper divisor for all positive integers
// Find divisors up to the square root of the number
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) { // Check if i is a divisor
sum += i; // Add the divisor
// Add the paired divisor (n / i) if it's not the same as i
if (i != n / i) {
sum += n / i;
}
}
}
// Check if the sum of divisors equals the number
return sum == n;
}
}
/**
* Problem: Check if a number is prime.
*
* Approach:
* 1. A number is prime if it has exactly two divisors: 1 and itself.
* 2. Count the number of divisors by iterating from 1 to n.
* 3. If the divisor count is exactly 2, return true (prime).
* Otherwise, return false (not prime).
*/
class Solution {
/* Function to find whether the
number is prime or not */
public boolean isPrime(int n) {
// Edge case: Numbers less than 2 are not prime
if (n < 2) return false;
/* Variable to store the
count of divisors of n */
int count = 0;
// Loop from 1 to n
for (int i = 1; i <= n; ++i) {
// Check if i is a divisor
if (n % i == 0) {
// Increment count
count++;
}
}
// If count is 2, n is prime
return count == 2;
}
public static void main(String[] args) {
int n = 5;
/* Creating an instance of
Solution class */
Solution sol = new Solution();
/* Function call to find whether the
given number is prime or not */
boolean ans = sol.isPrime(n);
if (ans) {
System.out.println(n + " is a prime number.");
} else {
System.out.println(n + " is not a prime number.");
}
}
}
// You are given an integer n. Your task is to determine the number of prime numbers in
// the range [1, n] (inclusive).
/*
Examples:
Example 1:
Input:
n = 6
Output:
3
Explanation:
The prime numbers in the range [1, 6] are 2, 3, and 5.
The count of prime numbers is 3.
Example 2:
Input:
n = 10
Output:
4
Explanation:
The prime numbers in the range [1, 10] are 2, 3, 5, and 7.
The count of prime numbers is 4.
Approach:
Helper Function - Check if a Number is Prime:
Create a helper function isPrime() to determine if a number is prime:
A number is prime if it has exactly two divisors: 1 and itself.
Use a loop to check the number of divisors.
Iterate through Range [1, n]:
Start a loop from 1 to n.
For each number, check if it is prime using the isPrime() function.
If the number is prime, increment the count.
Return Result:
After checking all numbers in the range, return the count of prime numbers.
*/
class Solution {
// Helper function to check if a number is prime
private boolean isPrime(int n) {
// Numbers less than 2 are not prime
if (n < 2) return false;
// Variable to store the count of divisors
int count = 0;
// Loop to count divisors
for (int i = 1; i <= n; ++i) {
if (n % i == 0) {
count++;
}
}
// A number is prime if it has exactly two divisors
return count == 2;
}
// Function to count the number of prime numbers in range [1, n]
public int primeUptoN(int n) {
// Variable to store the count of prime numbers
int count = 0;
// Iterate through all numbers in the range [1, n]
for (int i = 1; i <= n; i++) {
if (isPrime(i)) {
count++;
}
}
// Return the total count of prime numbers
return count;
}
public static void main(String[] args) {
int n = 10;
// Create an instance of Solution class
Solution sol = new Solution();
// Get the count of prime numbers in range [1, n]
int result = sol.primeUptoN(n);
// Print the result
System.out.println("Number of prime numbers in the range [1, " + n + "]: " + result);
}
}
/**
* Problem: Find the Greatest Common Divisor (GCD) of two numbers.
*
* Definition:
* The GCD of two integers is the largest positive integer that divides both integers without leaving a remainder.
*
* Examples:
* 1. Input: n1 = 4, n2 = 6
* Output: 2
* Explanation: Divisors of 4 are {1, 2, 4}. Divisors of 6 are {1, 2, 3, 6}.
* The greatest common divisor is 2.
*
* 2. Input: n1 = 9, n2 = 8
* Output: 1
* Explanation: Divisors of 9 are {1, 3, 9}. Divisors of 8 are {1, 2, 4, 8}.
* The greatest common divisor is 1.
*
* Approach:
* 1. Iterate through all numbers from 1 to min(n1, n2).
* 2. Check if a number divides both n1 and n2 without leaving a remainder.
* 3. Keep track of the largest such number, which is the GCD.
*/
class Solution {
/* Function to find the GCD of two numbers */
public int GCD(int n1, int n2) {
// Variable to store the GCD
int gcd = 1;
// Iterate from 1 to the smaller of n1 and n2
for (int i = 1; i <= Math.min(n1, n2); i++) {
// Check if i is a common divisor of both numbers
if (n1 % i == 0 && n2 % i == 0) {
// Update the GCD
gcd = i;
}
}
// Return the GCD
return gcd;
}
public static void main(String[] args) {
int n1 = 4, n2 = 6;
/* Creating an instance of
Solution class */
Solution sol = new Solution();
/* Function call to find the
gcd of two numbers */
int ans = sol.GCD(n1, n2);
// Print the result
System.out.println("GCD of " + n1 + " and " + n2 + " is: " + ans);
}
}
/**
* Problem: Find all divisors of a number.
*
* Definition:
* A divisor of a number is an integer that divides the number completely without leaving a remainder.
*
* Examples:
* 1. Input: n = 6
* Output: [1, 2, 3, 6]
* Explanation: Divisors of 6 are {1, 2, 3, 6}.
*
* 2. Input: n = 10
* Output: [1, 2, 5, 10]
* Explanation: Divisors of 10 are {1, 2, 5, 10}.
*
* Approach:
* 1. Loop through numbers from 1 to n.
* 2. Check if the number divides n without leaving a remainder.
* 3. If true, add the number to the list of divisors.
* 4. Return the list of divisors in sorted order.
*/
import java.util.ArrayList;
import java.util.List;
class Solution {
/* Function to find all divisors of a number */
public List<Integer> findDivisors(int n) {
// List to store divisors
List<Integer> divisors = new ArrayList<>();
// Iterate from 1 to n
for (int i = 1; i <= n; i++) {
// Check if i is a divisor of n
if (n % i == 0) {
// Add i to the list of divisors
divisors.add(i);
}
}
// Return the list of divisors
return divisors;
}
public static void main(String[] args) {
int n = 10;
/* Creating an instance of
Solution class */
Solution sol = new Solution();
/* Function call to find all
divisors of the given number */
List<Integer> divisors = sol.findDivisors(n);
// Print the divisors
System.out.println("Divisors of " + n + " are: " + divisors);
}
}
/**
* Problem: Find the Lowest Common Multiple (LCM) of two numbers.
*
* Definition:
* The Lowest Common Multiple (LCM) of two integers is the smallest positive integer
* that is divisible by both the integers.
*
* Examples:
* 1. Input: n1 = 4, n2 = 6
* Output: 12
* Explanation: 4 * 3 = 12, 6 * 2 = 12.
* 12 is the lowest integer that is divisible by both 4 and 6.
*
* 2. Input: n1 = 3, n2 = 5
* Output: 15
* Explanation: 3 * 5 = 15, 5 * 3 = 15.
* 15 is the lowest integer that is divisible by both 3 and 5.
*
* Approach:
* 1. Calculate the Greatest Common Divisor (GCD) of the two numbers.
* 2. Use the relationship between GCD and LCM: LCM(a, b) = (a * b) / GCD(a, b).
* 3. Return the calculated LCM.
*/
class Solution {
/* Function to calculate the GCD of two numbers using the Euclidean algorithm */
public int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
/* Function to calculate the LCM of two numbers */
public int findLCM(int n1, int n2) {
// Calculate the GCD of n1 and n2
int gcd = gcd(n1, n2);
// Use the LCM formula: LCM(a, b) = (a * b) / GCD(a, b)
return (n1 * n2) / gcd;
}
public static void main(String[] args) {
// Sample inputs
int n1 = 4, n2 = 6;
// Creating an instance of the Solution class
Solution sol = new Solution();
// Function call to find the LCM of the given numbers
int lcm = sol.findLCM(n1, n2);
// Print the LCM
System.out.println("LCM of " + n1 + " and " + n2 + " is: " + lcm);
}
}