import java.util.ArrayList;
public class SieveOfEratosthenes {
public static ArrayList<Integer> findPrimes(int n) {
// Step 1: Initialize a boolean array to keep track of prime numbers
boolean[] isPrime = new boolean[n + 1];
for (int i = 2; i <= n; i++) {
isPrime[i] = true; // Assume all numbers from 2 to n are prime initially
}
// Step 2: Apply the sieve algorithm
for (int p = 2; p * p <= n; p++) {
if (isPrime[p]) {
// Mark all multiples of p as non-prime
for (int multiple = p * p; multiple <= n; multiple += p) {
isPrime[multiple] = false;
}
}
}
// Step 3: Collect all prime numbers into an ArrayList
ArrayList<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
primes.add(i); // Add prime number to the list
}
}
return primes; // Return the sorted ArrayList of primes
}
public static void main(String[] args) {
int n = 50; // Example: Find all primes up to 50
ArrayList<Integer> primes = findPrimes(n);
System.out.println("Prime numbers up to " + n + ": " + primes);
}
}
Time Complexity Analysis
The algorithm consists of three main parts:
Step 1: Initializing the Boolean Array
We initialize an array of size n + 1 and set all values to true.
This requires a single loop that runs O(n) times.
Step 2: Marking Non-Prime Numbers
We iterate from p = 2 to √n. If p is prime, we mark all multiples of p starting from p² as non-prime.
The number of times a number is marked reduces significantly for higher values of p.
Time Complexity:O(n log log n)
Step 3: Collecting Prime Numbers
We loop through the isPrime array and add numbers that are still true to the result list.
This runs in O(n) time
Space Complexity Analysis
Boolean isPrime array:
Takes O(n) space.
ArrayList primes storing prime numbers:
The number of primes up to n is approximately O(n / log n).
Space Complexity:O(n / log n).
Overall Space Complexity: O(n)
Program to Swap Two Numbers
Approaches based on time and space complexity
Creating an temporary variable.
int temp = a;
a = b;
b = temp;
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)
a = a+b;
b = a-b;
a = a-b;
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
a = a ^ b;
b = a ^ b;
a = a ^ b;
Illustration:
a = 5 = 0101 (In Binary)
b = 7 = 0111 (In Binary)
Bitwise XOR Operation of 5 and 7
0101
^ 0111
________
0010 = 2 (In decimal)
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
public static void decimalToBinary(int n)
{
// array to store binary number
int[] binaryNum = new int[1000];
// counter for binary array
int i = 0;
while (n > 0)
{
// storing remainder in binary array
binaryNum[i] = n % 2;
n = n / 2;
i++;
}
// printing binary array in reverse order
for (int j = i - 1; j >= 0; j--)
System.out.print(binaryNum[j]);
}
Using Bitwise Operators
public void decToBinary(int n)
{
// Size of an integer is assumed to be 32 bits
for (int i = 31; i >= 0; i--) {
int k = n >> i;
if ((k & 1) > 0)
System.out.print("1");
else
System.out.print("0");
}
}
Bitwise operators work faster than arithmetic operators used in above methods
Without using arrays
public static int decimalToBinary(int decimalNumber) {
int binaryNumber = 0;
while (decimalNumber > 0) {
int remainder = decimalNumber % 2;
binaryNumber = (binaryNumber * 10) + remainder;
decimalNumber = decimalNumber / 2;
}
return binaryNumber;
}
Input first binary number: 10
Input second binary number: 11
Expected Output: Sum of two binary numbers: 101
Method 1: Using inbuilt method
long binary1 = 10L, binary2 = 11L;
// Parse binary strings as BigIntegers
BigInteger num1 = new BigInteger(String.valueOf(binary1), 2); // 2
BigInteger num2 = new BigInteger(String.valueOf(binary2), 2); // 3
// Add the two BigIntegers
BigInteger sum = num1.add(num2);
// Convert the result to binary string
String result = sum.toString(2);
// Print the result
System.out.println("Sum of two binary numbers: " + result);
Method 2: Using Modulo Division
// Declare variables to store two binary numbers, an index, and a remainder
long binary1, binary2;
int i = 0, remainder = 0;
// Create an array to store the sum of binary digits
int[] sum = new int[20];
// Create a Scanner object to read input from the user
Scanner in = new Scanner(System.in);
// Prompt the user to input the first binary number
System.out.print("Input first binary number: ");
binary1 = in.nextLong();
// Prompt the user to input the second binary number
System.out.print("Input second binary number: ");
binary2 = in.nextLong();
// Perform binary addition while there are digits in the binary numbers
while (binary1 != 0 || binary2 != 0)
{
// Calculate the sum of binary digits and update the remainder
sum[i++] = (int)((binary1 % 10 + binary2 % 10 + remainder) % 2);
remainder = (int)((binary1 % 10 + binary2 % 10 + remainder) / 2);
binary1 = binary1 / 10;
binary2 = binary2 / 10;
}
// If there is a remaining carry, add it to the sum
if (remainder != 0) {
sum[i++] = remainder;
}
// Decrement the index to prepare for printing
--i;
// Display the sum of the two binary numbers
System.out.print("Sum of two binary numbers: ");
while (i >= 0) {
System.out.print(sum[i--]);
}
Multiply two binary numbers given in long format
Input first binary number: 10
Input second binary number: 11
Expected Output: Sum of two binary numbers: 110
Method 1: Using inbuilt method
long longBinary1 = 10L, longBinary2 = 11L;
BigInteger binary1 = new BigInteger(String.valueOf(longBinary1),2); // 2
BigInteger binary2 = new BigInteger(String.valueOf(longBinary2),2); // 3
BigInteger result = binary1.multiply(binary2);
System.out.println(result.toString(2)); // 110
System.out.println(result.toString(10)); // 6
Method 2: Using Modulo operation
public static void main(String[] args) {
long longBinary1 = 10L, longBinary2 = 11L;
int sum, idx=0, position=0;
int[] result = new int[16]; // Assume max 16 bit
while(longBinary2!=0) {
sum = (int) (longBinary1*(longBinary2%10));
position = add(result, sum, idx);
idx++;
longBinary2 = longBinary2/10;
}
position--;
while(position>=0) {
System.out.print(result[position]);
position--;
}
}
private static int add(int[] result, int sum, int idx) {
sum = (int) (sum*Math.pow(10,idx));
int j = 0, carry = 0;
while (sum != 0) {
int tmp = result[j] + sum%10 + carry;
result[j] = tmp%2;
carry = tmp/2;
j++;
sum = sum/10;
}
return j;
}
Factorial of a number
Small number
Iterative Solution
static int findFactorial(int n) {
int factorial = 1;
while (n > 0) {
factorial = factorial * n;
n--;
}
return factorial;
}
Time Complexity: O(n)
Auxiliary Space: O(1)
Using Recursive Method
static int findFactorialUsingRecursiveMethod(int n) {
if (n == 0) {
return 1;
}
return findFactorialUsingRecursiveMethod(n-1)*n;
}
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.
Using Stream
public static long factorialUsingStreams(int n) {
return LongStream.rangeClosed(1, n)
.reduce(1, (a, b) -> a * b);
}
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.
static String findFactorialOfLargeNumber(int a) {
int[] result = new int[400];
result[0] = 1;
int result_size = 1;
for(int i=2; i<=a; i++) {
int carry = 0;
for(int j=0; j<result_size; j++) {
int product = result[j]*i + carry;
result[j] = product%10;
carry = product/10;
}
while(carry != 0) {
result[result_size] = carry%10;
carry = carry/10;
result_size++;
}
}
String reverseFactorial = Arrays.stream(result)
.mapToObj(String::valueOf)
.limit(result_size)
.collect(Collectors.joining());
return new StringBuilder(reverseFactorial).reverse().toString();
}
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
package src.main.java;
public class Application {
public static void main(String[] args) {
int n = 5;
printPascalTriangle(n);
}
static void printPascalTriangle(int n) {
for (int i=0; i<=n; i++) {
// Print initial whitespace
for (int j=i; j<n; j++) {
System.out.print(" ");
}
for (int k=0; k<=i; k++) {
int value = factorial(i)/(factorial(k)*factorial(i-k));
System.out.print(" " + value);
}
System.out.println();
}
}
static int factorial(int a) {
if (a <= 1) {
return 1;
}
return a*factorial(a-1);
}
}
Time complexity: O(2n) due to recursive method
Auxiliary Space: O(n) due to recursive stack space
Using Binomial Coefficient
Method 1:
// Function to calculate binomial coefficient C(n, k)
public static int binomialCoefficient(int n, int k) {
if (k == 0 || k == n) {
return 1;
}
return binomialCoefficient(n - 1, k - 1) + binomialCoefficient(n - 1, k);
}
// Function to generate Pascal's Triangle
public static void generatePascalsTriangle(int numRows) {
for (int i = 0; i < numRows; i++) {
for (int j = 0; j <= i; j++) {
System.out.print(binomialCoefficient(i, j) + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int numRows = 5; // Number of rows to generate
generatePascalsTriangle(numRows);
}
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).
public static void printPascal(int k)
{
for (int line = 1; line <= k; line++) {
for (int b = 0; b <= k - line; b++) {
// Print whitespace for left spacing
System.out.print(" ");
}
// Variable used to represent C(line, i)
int C = 1;
for (int a = 1; a <= line; a++) {
// The first value in a line is always 1
System.out.print(C + " ");
C = C * (line - a) / a;
}
// By now, we are done with one row so
// a new line is required
System.out.println();
}
}
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
public static void printFibonacci(int n) {
int a = 0, b = 1;
for (int i = 0; i < n; i++) {
System.out.print(a + " ");
int sum = a + b;
a = b;
b = sum;
}
}
Using Recursive Method
public static int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
public static void printFibonacci(int n) {
for (int i = 0; i < n; i++) {
System.out.print(fibonacci(i) + " ");
}
}
Print number triangle
int n = 4;
for(int line=1;line<=n;line++){
// Print spaces
for (int k=1; k<=n-line; k++) {
// First number space
System.out.print(" ");
// 2 Spaces between number
System.out.print(" ");
}
int columns = 2*line-1;
int value = line;
for(int i=1; i<=columns; i++){
System.out.print(" " + value);
if(i <= columns/2) {
value++;
} else {
value--;
}
}
// Go to new line
System.out.println();
}
Find Transpose of Matrix
Square Matrix
Method 1: Using additional array
static void transpose(int A[][], int B[][])
{
int i, j;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
B[i][j] = A[j][i];
}
Method 2: WIthout using additional array
for (int row=0;row<arr.length;row++){
for (int column=row;column<arr.length;column++){
int tmp = arr[row][column];
arr[row][column] = arr[column][row];
arr[column][row] = tmp;
}
}
Rectangular Matrix
int[][] arr = {{1,2,3},{4,5,6}};
int rows = 2;
int columns = 3;
int[][] transpose = new int[columns][rows];
// Print
for (int[] i : arr) {
for (int j : i) {
System.out.print(j + " ");
}
System.out.println();
}
for (int row=0;row<rows;row++){
for (int column=0;column<columns;column++){
transpose[column][row] = arr[row][column];
}
}
// Print
for (int[] i : transpose) {
for (int j : i) {
System.out.print(j + " ");
}
System.out.println();
}
GCD or HCF of two numbers
Using Iteration
int gcd(int a, int b) {
int result = Math.min(a,b);
while(result>0){
if (a%result==0 && b%result==0) {
return result;
}
result--;
}
return 1;
}
Time Complexity: O(min(a,b))
Auxiliary Space: O(1)
Using Euclidean algorithm for GCD of two numbers (Involves Recursion)
// Recursive function to return gcd of a and b
int gcd(int a, int b)
{
// All divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// Base case
if (a == b)
return a;
// a is greater
if (a > b)
return gcd(a - b, b);
return gcd(a, b - a);
}
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
int gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// Base case
if (a == b)
return a;
// a is greater
if (a > b) {
if (a % b == 0)
return b;
return gcd(a - b, b);
}
if (b % a == 0)
return a;
return gcd(a, b - a);
}
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.
// Recursive function to return gcd of a and b
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
Time Complexity: O(log(min(a,b)))
Auxiliary Space: O(log(min(a,b))
Iterative implementation using Euclidean Algorithm
int gcd(int a, int b)
{
while (a > 0 && b > 0) {
if (a > b) {
a = a % b;
}
else {
b = b % a;
}
}
if (a == 0) {
return b;
}
return a;
}
Time Complexity: O(log(min(a,b)))
Auxiliary Space: O(1)
Using in-built function in Java for BigIntegers
public static int gcd(int a, int b)
{
BigInteger bigA = BigInteger.valueOf(Math.abs(a));
BigInteger bigB = BigInteger.valueOf(Math.abs(b));
BigInteger gcd = bigA.gcd(bigB);
return gcd.intValue();
}
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
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Return LCM of two numbers
int lcm(int a, int b)
{
return (a / gcd(a, b)) * b;
}
Time Complexity: O(log(min(a,b))
Auxiliary Space: O(log(min(a,b))
Using Iterative method
int findLCM(int a, int b)
{
int greater = Math.max(a, b);
int smallest = Math.min(a, b);
for (int i = greater;; i += greater) {
if (i % smallest == 0)
return i;
}
}
Time Complexity: O(min(a,b))
Auxiliary Space: O(1)
Find All Factors of a Number
public static List<Integer> getAllFactors(int number) {
List<Integer> factors = new ArrayList<>();
for (int i = 1; i <= Math.sqrt(number); i++) {
if (number % i == 0) {
factors.add(i); // Add the smaller factor
if (i != number / i) {
factors.add(number / i); // Add the larger factor
}
}
}
factors.sort(Integer::compareTo); // Sort factors in ascending order
return factors;
}
