LeetCode Weekly Contest 479 Discussion and Solution

Problem-by-Problem Breakdown

Problem 1 - Sort Integers by Binary Reflection

Problem Statement

Approach

1. For each number in nums, convert it to binary, reverse it, and convert it back to decimal.
2. I stored both the original index and the binary reflection in a 2D helper array.
3. Then I sorted this array first by the reflection value, and if two reflections matched, by the original number.
4. Using the stored indexes, I rebuilt the sorted result.

Java Code

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

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

            n /= 2;
        }

        int num = 0;

        int len = sb.length();

        for(int i = len - 1; i >= 0; i--){
            if(sb.charAt(i) == '1'){
                num += (int) Math.pow(2, len - i - 1);
            }
        }

        return num;
    }
    public int[] sortByReflection(int[] nums) {
        int n = nums.length;

        int[][] rev = new int[n][2];
        int[] ans = new int[n];

        for(int i = 0; i < n; i++){
            int revNum = getRev(nums[i]);
            rev[i][0] = revNum;
            rev[i][1] = i;
        }

        Arrays.sort(rev, (a, b) -> a[0] == b[0] ? nums[a[1]] - nums[b[1]] : a[0] - b[0]);

        for(int i = 0; i < n; i++){
            ans[i] = nums[rev[i][1]];
        }


        return ans;
    }
}

Problem 2 - Largest Prime from Consecutive Prime Sum

Problem Statement

Approach

1. Generate prime numbers starting from 2.
2. Keep adding them cumulatively.
3. If at any point the cumulative sum becomes a prime and ≤ n, update the answer.
4. Continue until the sum exceeds n.

Java Code

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

        return true;
    }
    public int largestPrime(int n) {
        int sum = 0;
        int ans = 0;

        for(int i = 2; i <= n; i++){
            if(isPrime(i)){
                sum += i;
                if(sum > n) break;
                if(isPrime(sum)) ans = sum;
            }
        }

        return ans;
    }
}

Problem 3 - Total Score of Dungeon Runs

Problem Statement

Approach

1. deduct damage[i],
2. check if hp >= requirement[i], then gain a point.

Java Code

class Solution {
    public long totalScore(int hp, int[] damage, int[] requirement) {
        int n = damage.length;
        long ans = 0;

        for(int i = 0; i < n; i++){
            int currHp = hp;

            for(int j = i; j < n; j++){
                currHp -= damage[j];
                if(requirement[j] <= currHp) ans++;
            }
        }

        return ans;
    }
}

Problem 4 - Maximum Subgraph Score in a Tree

Problem Statement

Approach

class Solution {
    public int getScore(int curr, List<Integer>[] adj, boolean[] vis, int[] good){

        int score = good[curr] == 1 ? 1 : -1;
        vis[curr] = true;

        for(int i = 0; i < adj[curr].size(); i++){
            int next = adj[curr].get(i);
            if(vis[next]) continue;
            int sc = getScore(next, adj, vis, good);
            if(sc > 0) score += sc;
        }

        return score;
    }
    public int[] maxSubgraphScore(int n, int[][] edges, int[] good) {
        List<Integer>[] adj = new ArrayList[n];

        for(int i = 0; i < n; i++){
            adj[i] = new ArrayList<>();
        }

        for(int[] e : edges){
            int a = e[0];
            int b = e[1];

            adj[a].add(b);
            adj[b].add(a);
        }

        int[] ans = new int[n];

        for(int i = 0; i < n; i++){
            int score = getScore(i, adj, new boolean[n], good);
            ans[i] = score;
        }

        return ans;
    }
}

My Contest Experience