Can someone please tell me why my solution does not work/


  • 0
    A

    i have tried to model my solution after my ugly number 2 solution

    public class Solution {
        public int nthUglyNumber(int n) {
       
       if (n <= 0) {
                return 0;
            }
             
            List<Integer> nums = new ArrayList<>();
            nums.add(1);
             
            int i = 0;
            int j = 0;
            int k = 0;
             
            while (nums.size() < n) {
                int m2 = nums.get(i) * 2;
                int m3 = nums.get(j) * 3;
                int m5 = nums.get(k) * 5;
                 
                int mn = Math.min(Math.min(m2, m3), m5);
                nums.add(mn);
                 
                if (mn == m2) {
                    i++;
                }
                 
                if (mn == m3) {
                    j++;
                }
                 
                if (mn == m5) {
                    k++;
                }
            }
             
            return nums.get(nums.size() - 1);
        }
    
        
        
    }
    

    and here is my approach for super ugly number, but it gives the wrong answer.

    public class Solution {
        public int nthSuperUglyNumber(int n, int[] primes) {
    
    if (n <= 0) {
                return 0;
            }
        // create list to hold result and add 1 at the beginning 
        List<Integer> nums = new ArrayList<>();
        nums.add(1);
        
        Map<Integer,Integer> counter = new HashMap<Integer,Integer>();
        // put count as 0 for each prime
        for(int p : primes)
            counter.put(p,0);
        // untill the list has n elements 
        while (nums.size() < n) {
            
            int min=Integer.MAX_VALUE;int mk=0;
            //find min corresponding to each prime and increase its count
            for(Map.Entry<Integer,Integer> e : counter.entrySet())
            {
                int m = nums.get(e.getValue())*e.getKey();
                //System.out.println("m is "+m);
                if(m<=min)
                {
                    min=m;mk=e.getKey();
                    
                }
            }
            //System.out.println("min is "+min+ " from "+mk);
        
            nums.add(min);
            
            counter.put(mk,counter.get(mk)+1);
            /*for(Map.Entry<Integer,Integer> e : counter.entrySet())
            {System.out.println(e.getKey()+" "+e.getValue());}*/
        }
         
        return nums.get(nums.size() - 1);
    
    
     }
    }

  • 1
    M

    The way you update count is wrong. You need to update all count(index) of primes that reach the min value. Sometimes there may not be just one prime.

    For example, let's say primes = [2,7], when you try and locate 14 is the min, you need to update the count of both 2 and 7. That's exactly what this piece of code in nthUglyNumber is doing:

     if (mn == m2) {
                i++;
            }
    
            if (mn == m3) {
                j++;
            }
    
            if (mn == m5) {
                k++;
            }

  • 0
    A

    perfect! thanks


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.