Set 1 - Maths theory & Pattern
Program to Swap Two Numbers
Approaches based on time and space complexity
Creating an temporary variable.
Time Complexity: O(1) - Constant time. This is because the swapping operation only involves a few assignment statements, which are independent of the input size (number size).
Space Complexity: O(1) - Constant space. Only a single temporary variable is used, regardless of the size of the numbers being swapped.
Using maths addition and subtraction (Without Using Third Variable)
Time Complexity: O(1) - Constant time. Similar to the temporary variable approach, this method involves a fixed number of operations regardless of the input size.
Space Complexity: O(1) - Constant space. No additional memory is allocated beyond the variables holding the numbers.
Using exclusive OR (Bitwise XOR) operator
This is the most optimal method as here directly computations are carried on over bits instead of bytes as seen in above two methods
Time Complexity: O(1) - Constant time. Like the previous approaches, this method has a fixed number of operations.
Space Complexity: O(1) - Constant space. No extra memory is used beyond the variables holding the numbers.
Convert Decimal number to Binary number
There are many approaches.
Using Arrays
Using Bitwise Operators
Bitwise operators work faster than arithmetic operators used in above methods
Without using arrays
Convert Binary number to Decimal number
Using Math.pow(...) function
Factorial of a number
Small number
Iterative Solution
Time Complexity: O(n) Auxiliary Space: O(1)
Using Recursive Method
Time Complexity: O(n) Auxiliary Space: O(n)
The above solutions cause overflow for large numbers.
A factorial of 100 has 158 digits and it is not possible to store these many digits even if we use long int.
Large number
Using BigIntegers
Time Complexity: O(N) Auxiliary Space: O(1)
Using Basic Maths Operation with the help of array i.e. storing digits in array and considering carry which helps in increasing size of array.
Time Complexity: O(N log (N!)), where O(N) is for loop and O(log N!) is for nested while loop Auxiliary Space: O(max(digits in factorial))
Print Pascal Triangle
Using nCr formula
In this approach, we directly calculate the combinations using the formula .
Each entry in Pascal's Triangle corresponds to a specific combination , where is the row number and is the position within the row.
Time complexity: O(2n) due to recursive method
Auxiliary Space: O(n) due to recursive stack space
Using Binomial Coefficient
Method 1:
Method 2:
Using C = C * (line - a) / a
The ‘A’th entry in a line number line is Binomial Coefficient C(line, a) and all lines start with value 1. The idea is to calculate C(line, a) using C(line, a-1).
Time complexity: O(n^2) where n is given input for no of rows of pascal triangle
Auxiliary Space: O(1)
Print fibonacci series
Using Iterative Method
Using Recursive Method
Print number triangle
Find Transpose of Matrix
Square Matrix
Method 1: Using additional array
Method 2: WIthout using additional array
Rectangular Matrix
GCD or HCF of two numbers
Using Iteration
Time Complexity: O(min(a,b)) Auxiliary Space: O(1)
Using Euclidean algorithm for GCD of two numbers (Involves Recursion)
Time Complexity: O(min(a,b)) Auxiliary Space: O(1) No space is used as it is a tail recursion i.e. no extra space is used apart from the space needed for the function call stack.
Optimization Euclidean algorithm by checking divisibility
Time Complexity: O(min(a, b)) Auxiliary Space: O(1)
Optimization using division
Instead of the Euclidean algorithm by subtraction, a better approach is that we don’t perform subtraction but continuously divide the bigger number by the smaller number.
Time Complexity: O(log(min(a,b)))
Auxiliary Space: O(log(min(a,b))
Iterative implementation using Euclidean Algorithm
Time Complexity: O(log(min(a,b))) Auxiliary Space: O(1)
Using in-built function in Java for BigIntegers
Time Complexity: O(log(min(a, b))) Auxiliary Space: O(1)
LCM of two numbers
LCM (Least Common Multiple) of two numbers is the smallest number which can be divided by both numbers.
For example, LCM of 15 and 20 is 60, and LCM of 5 and 7 is 35.
Using GCD of 2 numbers and Formula
Time Complexity: O(log(min(a,b)) Auxiliary Space: O(log(min(a,b))
Using Iterative method
Time Complexity: O(min(a,b)) Auxiliary Space: O(1)
Check if String is Palindrome
A string is said to be a palindrome if it is the same if we start reading it from left to right or right to left. In this article, we will learn how to check if a string is a palindrome in Java.
Using Iteration Method
Time Complexity: O(n)
Space Complexity: O(n)
Using Improved Iteration Method
Time Complexity: O(n) (number of iterations is proportional to n/2 i.e. half of string)
Space Complexity: O(1)
Using String Builder
Time Complexity: O(n)
Space Complexity: O(n)
Using Recursion
This is like the two-pointer approach where we will check the first and the last value of the string.
Time Complexity: O(n), where n is the length of the input string. Function recursively calls itself for the characters at positions (i+1, j-1) until the pointers i and j cross each other or the characters at the pointers are not equal.
Space Complexity: O(n), where n is the length of the input string. This is because each recursive call creates a new stack frame that stores the current values of the function parameters and local variables. In the worst case, the function call stack may grow as large as n/2 (when the input string is a palindrome), so the space complexity is O(n).
Last updated