The Ugly Number also Hamming numbers, refer to the topcoder Problem Statement for HammingNumbers


  • 0
    T

    the problem is :
    Given a int[] of the chosen factors and an int n, return the n-th smallest Hamming number that can be obtained with these factors. n is 1-based, so the first number occurs when n = 1. If the result is above 2147483647 (32 bit signed integer maximum) then return -1.

    the Hamming numbers factors int[]{2,3,5}

    public int nthUglyNumber(int n) {
    		 
    		 return getNumber(new int[]{2,3,5},n);
    	    }
    
    
     public int getNumber(int[] factors, int n) {
    		    int m=factors.length;
    		    long[] res = new long[n];
    		    res[0] = 1;
    		    int[] index =new int[m];
    		    for (int i=1;i<n;i++) {
    		      long min = 2147483648L;
    		      int minj=-1;
    		      for (int j=0;j<factors.length;j++) {
    		        if (factors[j]*res[index[j]]<min) {
    		          min = factors[j]*res[index[j]];
    		          minj=j;
    		        }
    		      }
    		      if (minj<0) return -1;
    		      else {
    		        res[i]=min;
    		        for (int j=0;j<factors.length;j++) {
    		          if (factors[j]*res[index[j]]==min) index[j]++;
    		        }
    		        
    		      }
    		    }
    		    return (int)res[n-1];
    		  }

Log in to reply
 

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