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

  • 0

    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]];
    		      if (minj<0) return -1;
    		      else {
    		        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.