Thita DSA problems

basic dsa

Prime Numbers and Factorization: Find All Prime Factors

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public static List<Integer> getUniquePrimeFactors(int n) {
        List<Integer> factors = new ArrayList<>();
        
        // Step 1: Check the only even prime number (2)
        if (n % 2 == 0) {
            factors.add(2);
            while (n % 2 == 0) {
                n /= 2; // Keep dividing to remove all duplicate 2s
            }
        }
        
        // Step 2: Check odd factors up to the square root of n
        for (int factor = 3; factor * factor <= n; factor += 2) {
            if (n % factor == 0) {
                factors.add(factor);
                while (n % factor == 0) {
                    n /= factor; // Keep dividing to remove duplicate odd factors
                }
            }
        }
        
        // Step 3: If n is still greater than 1, the leftover n is prime
        if (n > 1) {
            factors.add(n);
        }
        
        return factors;
    }

    public static void main(String[] args) {
        // Test cases based on the problem description
        System.out.println(getUniquePrimeFactors(12)); // Output: [2, 3]
        System.out.println(getUniquePrimeFactors(30)); // Output: [2, 3, 5]
    }
}

GCD and LCM Calculator: Understanding Number Relationships

public class GcdLcmCalculator {
    
    // Method to calculate GCD using the Euclidean Algorithm
    public static int getGCD(int a, int b) {
        while (b != 0) {
            int remainder = a % b;
            a = b;         // The smaller number becomes the new 'a'
            b = remainder; // The remainder becomes the new 'b'
        }
        return a; // When b hits 0, 'a' holds the GCD
    }

    // Method to calculate LCM using the GCD shortcut
    public static int getLCM(int a, int b) {
        if (a == 0 || b == 0) {
            return 0; // Avoid division by zero
        }
        // We divide first to prevent the numbers from getting too huge
        return (a / getGCD(a, b)) * b;
    }

    public static void main(String[] args) {
        int num1 = 12;
        int num2 = 30;

        System.out.println("GCD of " + num1 + " and " + num2 + " is: " + getGCD(num1, num2)); // Output: 6
        System.out.println("LCM of " + num1 + " and " + num2 + " is: " + getLCM(num1, num2)); // Output: 60
    }
}

Modular Power Sum: Efficiently Compute (a^b + c^d) mod m

🛠 The Modular Fast Exponentiation Rule

To calculate \((a^b) \pmod m\) safely, you use the exact same three rules from fast exponentiation, but you apply % m every time you multiply or square a number. This keeps your variables from ever growing too large.

• Rule 1 (Odd Exponent): result = (result * base) % m

• Rule 2 (Always): base = (base * base) % m

• Rule 3 (Always): Halve the exponent (exponent /= 2)

public class ModularPowerSum {

    // Helper method to compute (base^exp) % m safely
    public static long modularExponentiation(long base, long exp, long m) {
        long result = 1;
        base = base % m; // Handle cases where base is larger than m

        while (exp > 0) {
            // Rule 1: If exponent is odd
            if (exp % 2 == 1) {
                result = (result * base) % m;
            }
            // Rule 2: Square the base
            base = (base * base) % m;
            
            // Rule 3: Halve the exponent
            exp /= 2;
        }
        return result;
    }

    // Main method to compute (a^b + c^d) % m
    public static long computePowerSum(long a, long b, long c, long d, long m) {
        long firstTerm = modularExponentiation(a, b, m);
        long secondTerm = modularExponentiation(c, d, m);
        
        // Add the two parts together and apply modulo one last time
        return (firstTerm + secondTerm) % m;
    }

    public static void main(String[] args) {
        // Example: Compute (2^10 + 3^5) % 7
        // 2^10 = 1024 -> 1024 % 7 = 2
        // 3^5 = 243   -> 243 % 7 = 5
        // (2 + 5) % 7 = 7 % 7 = 0
        long a = 2, b = 10;
        long c = 3, d = 5;
        long m = 7;

        System.out.println("Result: " + computePowerSum(a, b, c, d, m)); // Output: 0
    }
}

Count Set Bits in Range

public class Solution {
    // Helper method to count set bits of a single number in O(1) time
    private static int countSingleNumberBits(int n) {
        int count = 0;
        while (n > 0) {
            n = n & (n - 1); // Clears the lowest set bit
            count++;
        }
        return count;
    }

    // Main method to solve the range query requested
    public static int totalSetBitsInRange(int L, int R) {
        int totalCount = 0;
        
        // Loop through every number from L to R inclusive
        for (int i = L; i <= R; i++) {
            totalCount += countSingleNumberBits(i);
        }
        
        return totalCount;
    }

    public static void main(String[] args) {
        // Example test case from the problem description
        int L = 5; // 101 -> 2 bits
        int R = 7; // 6 is 110 (2 bits), 7 is 111 (3 bits)
        
        System.out.println(totalSetBitsInRange(L, R)); // Output: 7
    }
}

Efficient Power Calculation: Implement Fast Exponentiation

public class PowerSolution {

    // 1. Iterative Approach - O(log b) Time, O(1) Space
    public static long powerIterative(long a, int b) {
        // Base edge cases
        if (b == 0) return 1;
        if (a == 0) return 0;

        long result = 1;
        long base = a;
        long exponent = b;

        while (exponent > 0) {
            // Rule 1: If exponent is odd, multiply base to result
            if (exponent % 2 == 1) {
                result *= base;
            }
            // Rule 2: Square the base
            base *= base;
            // Rule 3: Halve the exponent
            exponent /= 2;
        }

        return result;
    }

    // 2. Recursive Approach - O(log b) Time, O(log b) Call Stack Space
    public static long powerRecursive(long a, int b) {
        // Base edge cases
        if (b == 0) return 1;
        if (a == 0) return 0;

        // Recursive call for half of the exponent
        long halfPower = powerRecursive(a, b / 2);

        // If exponent is even: (a^(b/2)) * (a^(b/2))
        if (b % 2 == 0) {
            return halfPower * halfPower;
        } 
        // If exponent is odd: a * (a^(b/2)) * (a^(b/2))
        else {
            return a * halfPower * halfPower;
        }
    }

    public static void main(String[] args) {
        int base = 3;
        int exponent = 13;

        System.out.println("Iterative Result (3^13): " + powerIterative(base, exponent)); // Output: 1594323
        System.out.println("Recursive Result (3^13): " + powerRecursive(base, exponent)); // Output: 1594323
    }
}

Divisibility Checker: Find the First Divisor

public class Solution {
    public static int getSmallestDivisor(int n) {
        // Step 1: Check the smallest possible divisor greater than 1
        if (n % 2 == 0) {
            return 2;
        }

        // Step 2: Check odd numbers up to the square root of n
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                return i; // Found the smallest divisor!
            }
        }

        // Step 3: If no divisor is found, n must be a prime number
        return n;
    }

    public static void main(String[] args) {
        // Example Test Cases
        System.out.println(getSmallestDivisor(12)); // Output: 2
        System.out.println(getSmallestDivisor(25)); // Output: 5
        System.out.println(getSmallestDivisor(17)); // Output: 17 (17 is prime)
    }
}