Basic Mathematics Data Structures and Algorithms

➤ Java Bean with Examples
➤ How to Code a Game
➤ Array Programs in Java
➤ Java Inline Thread Creation
➤ Java Custom Exception
➤ Hibernate vs JDBC
➤ Object Relational Mapping
➤ Check Oracle DB Size
➤ Check Oracle DB Version
➤ Generation of Computers
➤ XML Pros & Cons
➤ Git Analytics & Its Uses
➤ Top Skills for Cloud Professional
➤ How to Hire Best Candidates
➤ Scrum Master Roles & Work
➤ CyberSecurity in Python
➤ Protect from Cyber-Attack
➤ Solve App Development Challenges
➤ Top Chrome Extensions for Twitch Users
➤ Mistakes That Can Ruin Your Test Metric Program

Basic Mathematics Data Structures and Algorithms | Let us see some common and popular data structures and algorithms related to mathematics. We will also discuss the Sieve of Eratosthenes Algorithm and Euclidean algorithm.

Table of Contents

1. Basic Mathematics

a. Arithmetic and Geometric Progressions

Arithmetic Progression:-
2, 4, 6, 8, 10, ….
Common difference = 2. So the nth term is a + (n-1) * d where a is the starting number and d is the common difference.

The sum of terms:-
Average = sum / n
Sum = average * n
The average for evenly spaced numbers is given by (first term + last term) / 2.
So, sum = ( a + a + (n-1) * d) * n/2 = (2 * a + (n-1) * d) * n/2

b. Geometric Progressions

2, 4, 8, 16, 32, …
The ratio of two consecutive terms (r) = 2

So, considering the first term as a
2nd can be given as a * r
3rd term can be given as a * r2
Hence nth term = a * (rn-1)
Sum = (a * (rn - 1) ) / (r - 1)

c. Quadratic Equations

ax2 + bx + c = 0
D = b2 – 4ac
x = (-b +- sqrt(b2 - 4ac)) / 2a

If D < 0, then imaginary roots
If D = 0, two equal roots
If D > 0, two distinct roots

d. Mean and Median

Mean: The mean is found by adding up all of the given data and dividing by the number of data entries. Mean of 4, 1, and 7 = (4 + 1 + 7) / 3 = 12/3 = 4

Median: The middle number, found by ordering all data points and picking out the one in the middle (or if there are two middle numbers, taking the mean of those two numbers). Example:- Median of 4, 1, and 7 is 4 because when the number are put in order (1, 4, 7) then the number 4 is in the middle.

e. Factors

Factors: All the numbers that divide a number completely i.e. without leaving any remainder, are called factors of that number. Example:- 24 is completely divided by 1, 2, 3, 4, 6, 8, 12, 24. Each of these numbers is called a factor of 24 and 24 is called a multiple of each of these numbers.

f. Permutation & Combination

Permutation: It is defined as an arrangement of r things that can be done out of a total of N things. This is denoted by nPr, which equals n! / (n-r)! Where:-

  • n = Total number of items
  • r = Number of items to arrange

Example:- How many ways can you arrange 3 letters from a set of 5 letters (A, B, C, D, E)?
5P3 = 5! / (5 – 3)! = 5 × 4 × 3 = 60

Combination: Combination is the selection of r things that can be done out of total N things. This is denoted by nCr, which is equal to n! / ( r! (n - r)! ). Where:-

  • n = Total number of items
  • r = Number of items to select

Example:- How many ways can you choose 3 students from a group of 5?
5C3 = 5! / [3! × (5 – 3)!] = 10

Difference between nPr and nCr

  • nPr: Used when the order of arrangement matters (e.g., ranking 3 students out of 10).
  • nCr: Used when the order does not matter (e.g., choosing 3 students from 10 for a team).

g. Modular Arithmetic

  • The remainder obtained after the division operation on two operands is known as the modulo operation.
  • The operator for doing modulus operation is ‘%’. Example: 7%2 = 1, 17%3 = 2
  • In competitive programming, some of the questions are required to be answered in 10^7 modular. It is used to prevent overflow from integer values.

2. Count Digits in a Number

// iterative
public class Test {
    public static void main(String[] args) {
        int num = 12345;
        System.out.println(countDigits(num)); // 5
    }

    private static int countDigits(int num) {
        int digits = 0;
        while (num > 0) {
            digits++;
            num /= 10;
        }
        return digits;
    }
}
  • Time Complexity: O(d), where d is the number of digits in the input number.
  • Auxiliary Space Complexity: O(1).
// recursive
private static int countDigits(int num) {
    if (num == 0) {
        return 0;
    }
    return 1 + countDigits(num / 10);
}
  • Time Complexity: O(d), where d is the number of digits in the input number.
  • Auxiliary Space Complexity: O(d), since each recursive call adds a new stack frame.

The Math.log10(number) gives the logarithm base 10 of the number, which essentially counts the number of digits minus one. It returns double therefore cast the result to int to discard the decimal part. Adding one gives the total count of digits.

private static int countDigits(int num) {
    return (int) Math.log10(num) + 1;
}

Practice: Count the Digits That Divide a Number

3. Palindrome Number Check

If the reverse of the number is the same as the original number then it is a palindrome number. Example:- 78987. A single-digit number is always a palindrome number. Problem: 9

public class Test {
    public static void main(String[] args) {
        int num = 78987;
        System.out.println(palindromeCheck(num));
    }

    private static boolean palindromeCheck(int num) {
        if (num < 0) {
            return false;
        }
        int original = num, rev = 0;
        while (num > 0) {
            rev = rev * 10 + (num % 10);
            num /= 10;
        }
        return original == rev;
    }
}
  • Time Complexity: O(d). The while loop runs O(d) times, where d is the number of digits in the number.
  • Auxiliary Space Complexity: O(1). We use only a few integer variables, so the space complexity is O(1).

4. Prime Number

  • A number that can be divisible by only 1 and itself is called a prime number. Example:- 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, etc.
  • 2 and 3 are only two consecutive natural numbers which are prime too.
  • Every prime number can be represented in the form of 6n+1 or 6n-1 except 2 and 3, where n is the natural number. But its vice versa is not correct. Not all numbers of the form 6n + 1 or 6n – 1 are prime. Example:- 25 = 6*4 + 1 and 35 = 6*6 – 1

Divisors always appear in pairs. Example:-
30: (1, 3), (2, 15), (3, 10)
65: (1, 65), (5, 13)
25: (1, 25), (5, 5)

If (x, y) is a pair as x*y=n
And if x <= y
then x*x <= n
x <= sqrt(n)

Therefore consider the fact that the number N can’t have a divisor where the number is greater than the square root of N. Hence iterate from 2 to sqrt(n).

// check number is prime or not
public class Test {
    public static void main(String[] args) {
        int num = 21;
        System.out.println(isPrime(num));
    }

    private static boolean isPrime(int num) {
        if (num <= 1) return false;
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

Time Complexity: O(√n)
Auxiliary Space Complexity: O(1)

More efficient solution: We can reduce the number of iterations by adding extra checks. Idea:

  • By checking n%2 == 0 and n%3 == 0 we can save many iterations for large n.
  • Start from i=5 and increase to 6 in each iteration so that it can check for 11, 17, 23, etc.
  • In each iteration check for both i and i+2. The i+2 will handle the case for 7, 13, etc.
public class Test {
    public static void main(String[] args) {
        int num = 21;
        System.out.println(isPrime(num));
    }

    private static boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        if (n == 2 || n == 3) {
            return true;
        }
        if (n % 2 == 0 || n % 3 == 0) {
            return false;
        }
        for (int i = 5; i * i <= n; i = i + 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
}

Time Complexity: O(√n)
Auxiliary Space Complexity: O(1)

5. Prime Factors of a Given Number

Prime factors are those prime numbers that divide the given number. Examples:-
N = 12; Prime factors = 2, 2, 3
N = 13; Prime factors = 13
N = 315; Prime factors = 3, 3, 5, 7

Points to consider:-

  1. Divisors always appear in pairs. Example:- 30 = (1, 30), (2, 15), (3, 10), (5, 6). Therefore Pair can’t have a number greater than sqrt(n). So, we have to check for the prime factor from 2 to sqrt(n).
  2. A number N can be written as multiplications of power of prime factors. 12 = 22 × 31; 450 = 21 × 32 × 52; 13 = 131. Therefore check only for whether the number is divisible by a prime number or not.
public class Test {
    public static void main(String[] args) {
        int num = 21;
        printPrimeFactor(num);
    }

    private static void printPrimeFactor(int n) {
        if (n <= 1) {
            return;
        }
        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                System.out.print(i + " ");
                n = n / i;
            }
        }
        if (n > 1) {
            System.out.println(n); // prime number
        }
    }
}

Time Complexity: O(√n)
Auxiliary Space Complexity: O(1)

We can further optimize it like we have done while finding the prime number.

public class Test {
    public static void main(String[] args) {
        int num = 21;
        printPrimeFactor(num);
    }

    private static void printPrimeFactor(int n) {
        if (n <= 1) {
            return;
        }
        while (n % 2 == 0) {
            System.out.print(2 + " ");
            n /= 2;
        }
        while (n % 3 == 0) {
            System.out.print(3 + " ");
            n /= 3;
        }
        for (int i = 5; i * i <= n; i = i + 6) {
            while (n % i == 0) {
                System.out.print(i + " ");
                n = n / i;
            }
            while (n % (i + 2) == 0) {
                System.out.print((i + 2) + " ");
                n = n / (i + 2);
            }
        }
        if (n > 3) {
            System.out.println(n); // prime number
        }
    }
}

Time Complexity: O(√n)
Auxiliary Space Complexity: O(1)

6. Sieve of Eratosthenes

For a given number N, display all the prime numbers smaller than or equal to N. Problem: 204

I/P: n=10; O/P: 2 3 5 7
I/P: n=23; O/P: 2 3 5 7 9 11 13 17 19 23

A naive solution can be to iterate from 2 to N and check i is a prime number or not. The time complexity of this approach will be O(n * sqrt(n)).

Sieve of Eratosthenes is a classic algorithm for finding all primes up to a specified number. Here’s how it rolls:-

  • Make a Boolean array of length N+1. Initialize them with true. Don’t care first 2 indexes (0, and 1).
  • Start with the 3rd index in the array. 2 is a prime number. Leave array[2] to remain as true.
  • Mark all multiples of 2 from the array as false (expect array[2]).
  • Move to the next index in the array (3). It’s also prime. Leave array[3] to remain as true.
  • Mark all multiples of 3 from the array as false (except array[3]).
  • Repeat the process with the next index, and so on, until you’ve processed all indexes up to n’s square root.
  • At the end, array indexes with value=true are the prime numbers.

First let us see its simple implementation:-

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int num = 23;
        sieve(num); // 2 3 5 7 11 13 17 19 23 
    }

    private static void sieve(int n) {
        boolean[] isPrime = new boolean[n + 2];

        // mark evrey index as true
        Arrays.fill(isPrime, true);

        // skip 0 & 1 index
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                // start from j =2 * i, in each iteration move to j = j + i
                for (int j = 2 * i; j <= n; j = j + i) {
                    isPrime[j] = false;
                }
            }
        }

        // display indexes with value = true
        for (int i = 2; i < isPrime.length; i++) {
            if (isPrime[i]) {
                System.out.print(i + " ");
            }
        }
    }
}

Its optimized version:- In the second for loop, instead of starting from j = 2 * i, let us start from j = i * i. The reason the second for loop starts at j = i * i instead of j = 2 * i is efficiency. When we’re eliminating multiples of a prime i, we start at i * i because any smaller multiple of i (like 2 * i, 3 * i, etc.) would already have been marked as non-prime by smaller primes. This helps us avoid redundant operations and speeds up the algorithm.

Example of 5. We used to traverse 10, 15, 20, 25, 30, etc. But now j = i * i will traverse from 25, 30, 35, etc. So it will skip 10, 15, 20. As we can notice they were already marked as false by numbers < 3 because they are factors of 2 or 3. 

for (int i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
        // start from i * i
        for (int j = i * i; j <= n; j += i) {
            isPrime[j] = false;
        }
    }
}

Time Complexity: O(n log(log(n)))
Auxiliary Space Complexity: O(n)

7. Factorial of a Number

Factorial of a positive integer n, denoted by n! is the product of all positive integers less than or equal to n. Example: 5! = 5 * 4 * 3 * 2 * 1 = 120. Note that 0! = 1.

public class Test {
    public static void main(String[] args) {
        int num = 5;
        System.out.println(factorial(num));
    }

    private static long factorial(int num) {
        long res = 1;
        for (int i = 1; i <= num; i++) {
            res *= i;
        }
        return res;
    }
}

Time complexity O(n) and auxiliary space O(1).

// recursive
private static long factorial(int num) {
    if (num == 1) {
        return 1;
    }
    return num * factorial(num - 1);
}

Time complexity O(n) and auxiliary space O(n).

8. Trailing Zeros in Factorial

Count the trailing zeros in the factorial of a given number. Example:- 5! = 120 => Trailing zero = 1. 10! = 3628800 => Trailing zero = 2. Problem: 172

In the naive method, first, we find the factorial of the given number and we calculate the number of trailing zeros in the result. It will have time complexity O(n) and auxiliary space O(1). The issue with this problem is that it will cause overflow for a slightly large number because we are calculating the factorial. For example, the factorial of 20 is 2432902008176640000. If we go for a higher number then it causes the overflow.

The trailing zero in a factorial completely depends upon 2, 5. Therefore we should count the pair of (2, 5). However, the number of 5’s will be always less than the number of 2’s (because of 2, 4, 8, 12, ..). Therefore we just have to count the number of 5’s. Also note that some numbers will have more than one five like 25, 50, 75 which contains two 5’s. Hence:-

Trailing zero count = floor(n/5) + floor(n/25) + floor(n/125) + …….


public class Test {
    public static void main(String[] args) {
        int num = 251;
        System.out.println(countTrailingZeroInFactorial(num)); // 62
    }

    private static int countTrailingZeroInFactorial(int num) {
        int count = 0;
        for (int i = 5; i <= num; i = i * 5) {
            count += num / i;
        }
        return count;
    }
}

Time complexity O(log n) and auxiliary space O(1).

9. First Digit in Factorial

Instead of multiplying, we can sum the logarithms of these integers: log10(1 × 2 × 3 × … × n) = log10(1) + log10(2) + log10(3) + … + log10(n)

The total logarithm sum can be split into an integer part and a fractional part. The integer part represents the number of digits, while the fractional part helps determine the significant digit. By raising 10 to the power of the fractional part, we get a number between 1 and 10. The integer part of this number is the first digit.

public class Test {
    public static void main(String[] args) {
        System.out.println(factorialFirstDigit(5));
    }

    private static int factorialFirstDigit(int n) {
        if (n == 0) {
            return 1;
        }

        double factLog = 0;
        for (int i = 1; i <= n; i++) {
            factLog += Math.log10(i);
        }

        double fractionalPart = factLog - Math.floor(factLog);
        return (int) Math.pow(10, fractionalPart);
    }
}

10. All Divisors of a Number

Display all the divisors of a given number in the ascending order.

I/P: n = 15; O/P: 1 3 5 15
I/P: n = 100; O/P: 1 2 4 5 10 20 25 50 100
I/P: n = 7; O/P: 1 7

// naive solution
public class Test {
    public static void main(String[] args) {
        int num = 21;
        printDivisors(num);
    }

    private static void printDivisors(int n) {
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                System.out.print(i + " ");
                // 1 3 7 21
            }
        }

    }
}

Time complexity O(n) and auxiliary space O(1). Let us see how can we solve it in time complexity O(√n).

Points:-

  1. Divisors always appear in pairs. Example:- 30 = (1, 30), (2, 15), (3, 10), (5, 6). Therefore pair can’t have a number greater than sqrt(n).
  2. One of the divisors in every pair is smaller than or equal to sqrt(n).

The below program will give all the divisors but it won’t be in the ascending order. For 21 it will display 1 21 3 7.

private static void printDivisors(int n) {
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            System.out.print(i + " ");
            if (i != n / i) {
                System.out.print(n / i + " ");
            }
        }
    }
}

To display it in ascending order, we can do this:-

private static void printDivisors(int n) {
    int i;
    // print all divisors from 1 [inclusive] to sqrt(n) [exclusive]
    for (i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            System.out.print(i + " ");
        }
    }

    i--;

    // print all divisors from sqrt(n) [inclusive] to n [inclusive]
    for (; i >= 1; i--) {
        if (n % i == 0) {
            System.out.print(n / i + " ");
        }
    }
}

11. Greatest Common Divisor (GCD) or Highest Common Factor (HCF)

HCF of two or more given numbers is the highest number which exactly divides all the numbers. HCF of 12, and 16? Factors of 12: 1, 2, 3, 4, 6, 12. Factors of 16: 1, 2, 4, 8, 16. Common factors = 1, 2, 4. Hence HCF = 4

I/P: a=4, b=6; O/P: 2
I/P: a=100, b=200; O/P: 100
I/P: a=7, b=13; O/P: 1

// naive solution
public class Test {
    public static void main(String[] args) {
        System.out.println(hcf(4, 6));
    }

    private static int hcf(int a, int b) {
        int res = Math.min(a, b);
        while (res > 0) {
            if (a % res == 0 && b % res == 0) {
                return res;
            }
            res--;
        }
        return res;
    }
}

Time complexity O(min(a, b)), and auxiliary space O(1).

Euclidean Algorithm

Basic idea: Let b be smaller than a. gcd(a, b) = gcd(a-b, b). Why?
Let g be the GCD of a and b.
a = gx, b = gy and GCD(x, y) = 1
Then (a-b) = g(x-y)

public class Test {
    public static void main(String[] args) {
        System.out.println(hcf(12, 15));
    }

    private static int hcf(int a, int b) {
        while (a != b) {
            if (a > b) {
                a = a - b;
            } else {
                b = b - a;
            }
        }
        return a;
    }
}

For a=12, b=15
a=12, b=3
a=9, b=3
a=6, b=3
a=3, b=3

Instead of doing repeated subtraction, we can do modular division. Optimized version of Euclidean algorithm:-

private static int hcf(int a, int b) {
    if (b == 0) {
        return a;
    }
    return hcf(b, a % b);
}

hcf(12, 15)
hcf(15, 12)
hcf(12, 3)
hcf(3, 0)
=> 3

hcf(10, 15)
hcf(15, 10)
hcf(10, 5)
hcf(5, 0)
=> 5

Time complexity is O(log⁡(min⁡(a, b))) because with each recursive call, the size of the numbers involved is effectively halved (or reduced significantly), leading to a logarithmic number of operations.

12. LCM (Least Common Multiple) of two numbers

LCM (Least Common Multiple): The LCM of two or more numbers is the smallest number other than zero which is a multiple of each number. Example:- LCM of 4 and 6 => Multiple of 4: 4, 8, 12, 16, 20, .. Multiple of 6: 6, 12, 18, 24, … Common multiples: 12, 24. Hence LCM = 12. If both numbers are prime numbers then LCM = multiplication of both numbers.

// naive solution
public class Test {
    public static void main(String[] args) {
        System.out.println(lcm(12, 15));
    }

    private static int lcm(int a, int b) {
        int res = Math.max(a, b);
        while (true) {
            if (res % a == 0 && res % b == 0) {
                return res;
            }
            res++;
        }
    }
}

Time complexity O(a*b – max(a, b)), and auxiliary space O(1).

We can have an efficient solution by using GCD or HCF. As we know, a * b = gcd(a, b) * lcm (a, b).

public class Test {
    public static void main(String[] args) {
        System.out.println(lcm(12, 15));
    }

    private static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }

    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

Time complexity O(min(a, b)), and auxiliary space O(1).

13. Computing Pow(x, n)

For given two numbers x, and n, find xn.

I/P: x = 2, n = 3; O/P: 8
I/P: x = 3, n = 4; O/P: 81
I/P: x = 5, n = 0; O/P: 1
I/P: x = 5, n = 1; O/P: 5

The naive solution is to initialize the result as 1, iterate from 1 to n, and in each iteration result = result * x. Time complexity O(n). Let us see how it can be done in O(log n).

Assume we want to calculate x^40 and the result for x^20 is known to us then:-
x^40 can be calculated as x^20 * x^20;
And x^41 can be calculated as x * x^40 => x^20 * x^20;

Hence pow(x, n) can be calculated as:-
if n % 2 == 0: power(x, n/2) * power(x, n/2)
else: power(x, n-1) * x which can be written as x * power(x, n/2) * power(x, n/2)

public class Test {
    public static void main(String[] args) {
        System.out.println(power(3, 5));
    }

    private static long power(int x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }

        long half = power(x, n / 2);
        long squareOfHalf = half * half;

        return n % 2 == 0 ? squareOfHalf : x * squareOfHalf;
    }
}

Time complexity O(log n), space complexity O(log n).

14. Iterative Power (Binary Exponentiation)

Let us see the iterative approach to compute the power of a number. It is different from a recursive solution. It will have time complexity O(log n), and space complexity O(1). Problem: 50

Some facts:

  • Every number can be written as the sum of the power of 2 (set bits in binary representation). Example: 310 = 38 + 32 as 10 = “1010” in binary. Similarly, 319 = 316 + 32 + 31 as 19 = 10011.
  • We can traverse through all bits of a number (from LSB to MSB) in O(log n) time.
// to get the bits of number from LSB to MSB
while(n > 0) {
    if(n % 2 != 0) {
        // bit is 1
    } else {
        // bit is 0
    }
    n /= 2;
}

Every time we find a 1 bit then consider it as a multiplier of the corresponding power of x.

public class Test {
    public static void main(String[] args) {
        System.out.println(power(3, 5));
    }

    private static long power(int x, int n) {
        long res = 1;
        while (n > 0) {
            if (n % 2 != 0) {
                res = res * x;
            }
            x = x * x;
            n /= 2;
        }
        return res;
    }
}

Time complexity O(log n), and space complexity O(1).

If the result needs to be modular or 107 then we can do follows:-

public class Test {
    public static void main(String[] args) {
        System.out.println(power(3, 5, 10000000));
    }

    private static long power(int x, int n) {
        long res = 1;
        while (n > 0) {
            if (n % 2 != 0) {
                res = (res * x) % MOD;
            }
            x = (x * x) % MOD;
            n /= 2;
        }
        return res;
    }
}

To Handle the case N can be negative:-


public class Test {
    public static void main(String[] args) {
        System.out.println(power(3, 5)); // Expected output: 243
        System.out.println(power(3, -2));
        // Expected output: 0.1111111111111111 (which is 1/9)
    }

    private static double power(int x, int n) {
        double res = 1.0;
        if (x == 1.0) {
            return x;
        }
        if (x == -1.0) {
            return n % 2 == 0 ? -x : x;
        }
        if (n == Integer.MIN_VALUE) {
            return 0.00000;
        }
        int absN = Math.abs(n); // absolute value of n
        while (absN > 0) {
            if (absN % 2 != 0) {
                res *= x;
            }
            x = x * x;
            absN /= 2;
        }
        return n < 0 ? 1 / res : res;
    }
}

Also see:- Binary Exponentiation of Matrix, Fibonacci Number Using Matrix Exponentiation

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Leave a Comment

Your email address will not be published. Required fields are marked *