Test case fail at n=1485, I got a NEGATIVE result;but when I convert all number types into Long, the code passes..


  • 0

    Hello, I am new, so my code might not well-written and it's long..

    At first I derive the result assuming all numbers participated in the calculation are integers, and the code passed 590/596 tests; when n=1485, I get -1921920421. I don't know where I got wrong, so I change all number into Long type and it passes all tests..I don't know what's wrong.

    Integer calculation:

    import java.util.PriorityQueue;
    public class Solution{
    public int nthUglyNumber(int n){
    	if(n==1){
    		return 1;
    	}
    	
    	PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
    	heap.offer(2);
    	heap.offer(3);
    	heap.offer(5);
    
    	int i=0;
    	int res=0;
    	while(i<n-1){
    		i++;
    		res=heap.poll();
    		if(res%5==0){
    			if(res%3==0){
    				if(res%2==0){
    					heap.offer(res*2);
    					continue;
    				}else{
    					heap.offer(res*3);
    					heap.offer(res*2);
    					continue;
    				}
    				
    			}else{
    				if(res%2==0){
    					heap.offer(res*2);
    					continue;
    				}else{
    					heap.offer(res*5);
    					heap.offer(res*3);
    					heap.offer(res*2);
    					continue;
    				}
    			}
    		}
    
    		if(res%3==0){
    			if(res%2==0){
    				heap.offer(res*2);
    				continue;
    			}else{
    				heap.offer(res*2);
    				heap.offer(res*3);
    				continue;
    			}
    		}
    
    		if(res%2==0){
    			heap.offer(res*2);
    		}
    	}
    	return res;
    
    }
    
    public static void main(String[] args){
    	Solution s = new Solution();
    	System.out.println(s.nthUglyNumber(1485));
    }
    

    }

    Long calculation:

    import java.util.PriorityQueue;
    import java.lang.Long;
    
    public class Solution{
    public int nthUglyNumber(int n){
    	if(n==1){
    		return 1;
    	}
    	
    	PriorityQueue<Long> heap = new PriorityQueue<Long>();
    	Long fac2=Long.valueOf(2);
    	Long fac3=Long.valueOf(3);
    	Long fac5=Long.valueOf(5);
    
    	heap.offer(fac2);
    	heap.offer(fac3);
    	heap.offer(fac5);
    
    	int i=0;
    	Long res=0L;
    	while(i<n-1){
    		i++;
    		res=heap.poll();
    		if(res%fac5==0){
    			if(res%fac3==0){
    				if(res%fac2==0){
    					heap.offer(res*fac2);
    					continue;
    				}else{
    					heap.offer(res*fac3);
    					heap.offer(res*fac2);
    					continue;
    				}
    				
    			}else{
    				if(res%fac2==0){
    					heap.offer(res*fac2);
    					continue;
    				}else{
    					heap.offer(res*fac5);
    					heap.offer(res*fac3);
    					heap.offer(res*fac2);
    					continue;
    				}
    			}
    		}
    
    		if(res%fac3==0){
    			if(res%fac2==0){
    				heap.offer(res*fac2);
    				continue;
    			}else{
    				heap.offer(res*fac2);
    				heap.offer(res*fac3);
    				continue;
    			}
    		}
    
    		if(res%fac2==0){
    			heap.offer(res*fac2);
    		}
    	}
    	return res.intValue();
    
    }
    
    public static void main(String[] args){
    Solution s = new Solution();
    System.out.println(s.nthUglyNumber(1485));
    }
    

    }


  • 0
    D

    I'm new too, so this is just my best guess at the problem.
    When you do

     heap.offer(res*5)
    

    if res is large enough, it will go past Integer.MAX_VALUE and become negative. This would explain why converting it to a long made your code work as longs can store larger numbers.


Log in to reply
 

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