Algorithm: Leetcode Contest 382

This time I only solved one medium problem

Find the Maximum Number of Elements in Subset

My solution

public int maximumLength(int[] nums) {
    Arrays.sort(nums);

    Map<Integer, Integer> map = new HashMap<>();
    for(int num: nums) {
        if (!map.containsKey(num)) {
            map.put(num, 0);
        }

        map.put(num, map.get(num) + 1);
    }

    // 2. iterate the array, for each element,
    int idx = 0;
    int curBase = -1, curVal = 0, pow = 1, preVal = curVal;
    int res = 0, count = 0;
    while(idx < nums.length) {
        count = 0;
        pow = 1;

        if (curBase == nums[idx]) {
            idx++;
            continue;
        } else {
            curBase = nums[idx++];
        }

        curVal = (int) Math.pow(curBase, pow);
        pow *= 2;

        while(map.containsKey(curVal)) {
            count++;

            if (map.get(curVal) >= 2) {
                curVal = (int) Math.pow(curBase, pow);
                pow *= 2;
                if (map.containsKey(curVal)) {
                    count++;
                }
            } else {
                break;
            }
        }

        res = Math.max(res, count);
    }

    return res;
}

Approved Solution

public int maximumLength(int[] nums) {
    Map<Integer,Integer> nm=new HashMap<>();
    for(int i:nums)
    {
        nm.put(i, nm.getOrDefault(i,0)+1);
    }
    Arrays.sort(nums);
    int maxi= nm.containsKey(1) ? nm.get(1)%2 == 0 ? nm.get(1)-1 : nm.get(1) : 1; // what I missed
    for(int i=0;i<nums.length;i++)
    {
        int count=0;
        int val=nums[i];
        while(nm.containsKey(val) && nm.get(val)>=2 && val!=1)
        {
            count+=2;
            val*=val;
        }
        if(nm.containsKey(val))
        {
            count++;
        }
        else
        {
            count--;
        }
        maxi=Math.max(count,maxi);
    }
    return maxi;

}

Retro

I was failing to handle a special case where there are multiple 1, so I am struggling to find a general code to handle all cases.

actually this is a special case, I can handle multiple 1 separately. because my main code already works.