LeetCode Biweekly Contest 171 Discussion and Solution

Problem-by-Problem Breakdown

Problem 1 - Complete Prime Number

Problem Statement

• A prefix of a number is formed by the first k digits of the number.
• A suffix of a number is formed by the last k digits of the number.

Approach

1. I wrote a helper function isPrime() to check primality (this was the easy part).
2. The main challenge was generating all prefixes and suffixes.
3. For suffixes, I extracted digits one by one from the original number and kept building numbers.
4. For prefixes, I reversed the number and again extracted digits one by one.

Java Code

class Solution {
    public boolean isPrime(long 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 += 2){
            if(n % i == 0) return false;
        }

        return true;
    }
    public boolean completePrime(int num) {

        long org = num;
        long rev = 0;

        while(num > 0){
            int digit = num % 10;
            rev = rev * 10 + digit;
            num /= 10;
        }

        long n = 0;
        long m = 0;

        int power = 0;

        while(org > 0){
            long digit = org % 10;
            n = digit * (int) Math.pow(10, power) + n;
            power++;
            org /= 10;

            if(!isPrime(n)) return false;
        }

        while(rev > 0){
            long digit = rev % 10;
            m = m * 10 + digit;
            rev /= 10;

            if(!isPrime(m)) return false;
        }

        return true;
    }
}

Problem 2 - Minimum Operations to Make Binary Palindrome

Problem Statement

• Increase nums[i] by 1, or
• Decrease nums[i] by 1.

Approach

1. Find the nearest palindromic binary number greater than or equal to x
2. Find the nearest palindromic binary number less than or equal to x
3. Compute the operations (difference).
4. Store the minimum operations among the two

• to check if a binary representation is palindromic
• to search upward
• to search downward

Java Code

class Solution {
    public boolean checkPalin(int n){
        StringBuilder sb = new StringBuilder();

        while(n > 0){
            if(n % 2 == 0) sb.append('0');
            else sb.append('1');

            n /= 2;
        }

        int i = 0;
        int j = sb.length() - 1;

        while(i <= j){
            if(sb.charAt(i) != sb.charAt(j)){
                return false;
            }
            i++;
            j--;
        }

        return true;
    }

    public int countIncOpr(int n){
        int count = 0;

        while(!checkPalin(n)){
            count++;
            n++;
        }

        return count;
    }

    public int countDecOpr(int n){
        int count = 0;

        while(!checkPalin(n)){
            count++;
            n--;
        }

        return count;
    }
    public int[] minOperations(int[] nums) {
        int n = nums.length;

        int[] ans = new int[n];

        for(int i = 0; i < n; i++){
            int inc = countIncOpr(nums[i]);
            int dec = countDecOpr(nums[i]);

            ans[i] = Math.min(inc, dec);
        }

        return ans;
    }
}

Problem 3 - Maximize Points After Choosing K Tasks

Problem Statement

• If the ith task is completed using technique 1, you earn technique1[i] points..
• If it is completed using technique 2, you earn technique2[i] points.

Approach

1. For every task, I looked at, how much benefit I get if I choose Technique 1 instead of Technique 2
2. Based on this advantage value, I pushed tasks into a PriorityQueue (max-heap)
3. Then, Pick the top k tasks (where Technique 1 gives maximum advantage), complete these using Technique 1
4. For the remaining tasks, choose whichever technique gives more points

Java Code

class Solution {
    public class TaskPoint{
        int point;
        int idx;

        public TaskPoint(int point, int idx){
            this.point = point;
            this.idx = idx;
        }
    }
    public long maxPoints(int[] t1, int[] t2, int k) {
        int n = t1.length;
        
        PriorityQueue<TaskPoint> pq = new PriorityQueue<>((a, b) -> b.point - a.point);

        boolean[] completed = new boolean[n];
            
        
        for(int i = 0; i < n; i++){
            int point = t1[i] - t2[i];
            TaskPoint tp = new TaskPoint(point, i);
            pq.add(tp);
        }

        long ans = 0;

        while(k > 0 && !pq.isEmpty()){
            TaskPoint tp = pq.poll();
            completed[tp.idx] = true;
            ans += t1[tp.idx];
            k--;
        }

        for(int i = 0; i < n; i++){
            if(!completed[i]){
                ans += Math.max(t1[i], t2[i]);
            }
        }

        return ans;
    }
}

Problem 4 - Minimum Inversion Count in Subarrays of Fixed Length

Problem Statement

Approach

1. Take each subarray of size k
2. Count inversions inside it
3. For suffixes, I extracted digits one by one from the original number and kept building numbers.
4. For prefixes, I reversed the number and again extracted digits one by one.

My Contest Experience

1. How fast I catch the right direction
2. Avoiding typing errors
3. Handling edge cases quickly