Problems - Set 1

Prime Number

Apply Sieve of Eratosthenes Algorithm

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

1. Boolean isPrime array:

   • Takes O(n) space.

2. 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

1. 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.

1. 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.

1. 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;
}

Using inbuit method

long binary1 = 10L, binary2 = 11L;
int binary3 = 123;
String binaryStr1 = Long.toBinaryString(binary1); // 1010
String binaryStr2 = Long.toBinaryString(binary2); // 1011
String binaryStr3 = Integer.toBinaryString(binary3);

Convert Binary number to Decimal number

• Using Math.pow(...) function

public static int binaryToDecimal(int binaryNumber) {
    int decimalNumber = 0;
    for(int i=0; binaryNumber != 0; i++) {
       int remainder = binaryNumber % 10;
        decimalNumber = decimalNumber + ((int) (Math.pow(2, i)) * remainder);
        binaryNumber = binaryNumber / 10;
    }
    return decimalNumber;
}

Binary Arithmetic

Add two binary numbers given in long format

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);
}

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

Large number

Using BigIntegers

static BigInteger findFactorialOfLargeNumber(int a) {
    BigInteger bigInteger = BigInteger.ONE;
    for(int i=2; i<=a; i++){
        bigInteger = bigInteger.multiply(BigInteger.valueOf(i));
    }
    return bigInteger;
}

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.

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);
    }
}

Output

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;
    }