Basic Maths
Count all Digits of a Number
class Solution {
public int countDigit(int n) {
if (n == 0) return 1;
int digits = 0;
while (n != 0) {
n /= 10;
++digits;
}
return digits;
}
}The gist of the algorithm is to repeatedly divide the number by 10 to remove the last digit, while counting how many times this operation is performed. This count represents the total number of digits. An edge case for the input 0 is handled separately, returning 1.
Time Complexity: O(log₁₀(n)), as the number of iterations is proportional to the number of digits in n.
Space Complexity: O(1), as it uses a constant amount of extra space.
Count number of odd digits in a number
class Solution {
public int countOddDigit(int n) {
int odd = 0;
while (n != 0) {
int digit = n % 10;
if (digit % 2 == 1)
++odd;
n /= 10;
}
return odd;
}
}The algorithm iterates through each digit of the number. It extracts the last digit using the modulo operator (% 10) and checks if it's odd. The number is then divided by 10 to process the next digit, continuing until the number becomes 0.
Time Complexity: O(log₁₀(n)), where n is the input number, because the loop runs once for each digit.
Space Complexity: O(1).
Reverse a number
class Solution {
public int reverseNumber(int n) {
int rev = 0;
while (n != 0) {
rev *= 10;
int digit = n % 10;
rev += digit;
n /= 10;
}
return rev;
}
}This algorithm reverses an integer by iteratively extracting its last digit and building a new reversed number. In each step, the last digit is popped from the original number using the modulo operator and appended to the result by multiplying the result by 10 and adding the digit.
Time Complexity: O(log₁₀(n)), as it processes one digit per iteration.
Space Complexity: O(1).
Palindrome Number
class Solution {
public boolean isPalindrome(int n) {
int rev = 0;
int temp = n;
while (temp != 0) {
int digit = temp % 10;
rev = (rev * 10) + digit;
temp /= 10;
}
return rev == n;
}
}The approach is to first reverse the given number n and then compare the reversed number with the original. If they are identical, the number is a palindrome.
Time Complexity: O(log₁₀(n)), for reversing the number.
Space Complexity: O(1).
Return the Largest Digit in a Number
class Solution {
public int largestDigit(int n) {
int maxDigit = 0;
while (n != 0) {
int digit = n % 10;
maxDigit = Math.max(maxDigit, digit);
n /= 10;
}
return maxDigit;
}
}The algorithm iterates through each digit of the number by repeatedly taking the number modulo 10 and then dividing it by 10. It maintains a variable maxDigit to keep track of the largest digit encountered so far.
Time Complexity: O(log₁₀(n)), because the loop runs for each digit of the number.
Space Complexity: O(1).
Factorial of a given number
class Solution {
public int factorial(int n) {
int fact = 1;
for (int i = 2; i <= n; ++i) {
fact *= i;
}
return fact;
}
}This is an iterative solution to calculate the factorial. It initializes a variable fact to 1 and then multiplies it by each integer from 2 up to n.
Time Complexity: O(n), as the loop runs n-1 times.
Space Complexity: O(1).
Check if the Number is Armstrong
class Solution {
public boolean isArmstrong(int n) {
int digitNumber = 0;
int temp = n;
while (temp != 0) {
++digitNumber;
temp /= 10;
}
int candidate = 0;
temp = n;
while (temp != 0) {
int digit = temp % 10;
candidate += Math.pow(digit, digitNumber);
temp /= 10;
}
return candidate == n;
}
}The algorithm first calculates the number of digits in the input n. It then iterates through the digits of n again, calculating the sum of each digit raised to the power of the total number of digits. Finally, it checks if this sum equals the original number n.
Time Complexity: O(log₁₀(n)), because it involves two separate loops that each run for every digit in the number.
Space Complexity: O(1).
Check for Perfect Number
class Solution {
public boolean isPerfect(int n) {
if (n == 1) return false;
int divisorSum = 1;
for (int i = 2; i * i <= n; ++i) {
if (n % i != 0) continue;
divisorSum += i;
if (i * i == n) continue;
divisorSum += (n / i);
}
return divisorSum == n;
}
}The algorithm checks if a number is a perfect number, which is a positive integer that is equal to the sum of its proper positive divisors. It efficiently finds divisors by iterating up to the square root of n. For each divisor i, it also considers n/i.
Time Complexity: O(sqrt(n)), due to the loop condition i * i <= n.
Space Complexity: O(1).
Check for Prime Number
class Solution {
public boolean isPrime(int n) {
if (n == 1) return false;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) return false;
}
return true;
}
}This method uses trial division to check for primality. It iterates from 2 up to the square root of n. If it finds any number that divides n evenly, n is not prime. If the loop completes without finding any such divisor, n is prime.
Time Complexity: O(sqrt(n)).
Space Complexity: O(1).
Count of Prime Numbers till N
class Solution {
public int primeUptoN(int n) {
boolean[] prime = new boolean[n + 1];
Arrays.fill(prime, true);
prime[0] = false;
prime[1] = false;
for (int i = 2; i <= n; ++i) {
if (!prime[i]) continue;
for (int j = i * i; j <= n; j += i) {
prime[j] = false;
}
}
int count = 0;
for (int i = 0; i <= n; ++i) {
if (prime[i]) ++count;
}
return count;
}
}The algorithm uses the Sieve of Eratosthenes to find all prime numbers up to n. It initializes a boolean array indicating primality for all numbers up to n. It then iterates from 2 and for each prime number found, it marks all of its multiples as not prime. Finally, it counts the numbers still marked as prime.
Time Complexity: O(n * log(log(n))).
Space Complexity: O(n) for the boolean prime array.
GCD of Two Numbers
class Solution {
public int GCD(int n1, int n2) {
while (n2 != 0) {
int rem = n1 % n2;
n1 = n2;
n2 = rem;
}
return n1;
}
}This code implements the Euclidean algorithm to find the greatest common divisor (GCD) of two numbers. It repeatedly replaces the larger number with the remainder of the division of the two numbers until the second number becomes zero. The GCD is the last non-zero remainder.
Time Complexity: O(log(min(n1, n2))), as the numbers decrease exponentially.
Space Complexity: O(1).
LCM of two numbers
class Solution {
public int GCD(int n1, int n2) {
while (n2 != 0) {
int rem = n1 % n2;
n1 = n2;
n2 = rem;
}
return n1;
}
public int LCM(int n1, int n2) {
return (n1 / GCD(n1, n2)) * n2;
}
}The algorithm calculates the least common multiple (LCM) of two numbers using the formula LCM(a, b) = (|a * b|) / GCD(a, b). To avoid potential integer overflow, it's calculated as (a / GCD(a, b)) * b. It leverages the Euclidean algorithm for the GCD calculation.
Time Complexity: O(log(min(n1, n2))) dominated by the GCD calculation.
Space Complexity: O(1).
Divisors of a Number
class Solution {
public int[] divisors(int n) {
List<Integer> res = new ArrayList<>();
for (int i = 1; i * i <= n; ++i) {
if (n % i != 0) continue;
res.add(i);
if (i * i == n) continue;
res.add(n / i);
}
Collections.sort(res);
return res.stream().mapToInt(Integer::intValue).toArray();
}
}This method finds all divisors of a number n by iterating from 1 up to the square root of n. If i is a divisor, it adds both i and n/i to a list. This ensures all pairs of divisors are found. Finally, the list of divisors is sorted.
Time Complexity: O(sqrt(n) + d log d), where d is the number of divisors. The first term is for finding the divisors, and the second is for sorting them.
Space Complexity: O(d) to store the list of divisors.