UVA – 136 – Ugly Numbers

  • ID : UVA – 136 – Ugly Numbers
  • Submissions : Java – Accepted
  • Difficulty : Easy
  • Type : Number Theory , Factorization , Dynamic Programming
  • Time for Submission : 2 Hours
  • Solution Description :
    • this problem can be solved dynamically using the fact that any ugly number is composed of a previous ugly number, multiplied by  2, 3 or 5.
    • so you loop each time through all the previous ugly numbers  multiply each of them by 2, 3 & 5 and check which one is the least next one.
    • but for more optimization, you can keep track only of the most recent 3 numbers in-queue that when multiplied by one of the mentioned factors will produce a number that will come after the latest ugly number. and each time you find their minimum and advance its pointer
  • Problems :
    • No Problems, it went smoothly 🙂
  • Code :

public class Main {
	public static void main(String[] args) {
		int ugly[] = new int[1501], ps[]  = {1,1,1}, factors[]  ={ 2,3,5 };
		ugly[1] =1;

		for(int i=2; i<=1500;i++){
			ugly[i] = Math.min(2*ugly[ps[0]], Math.min(3*ugly[ps[1]], 5*ugly[ps[2]]));

			for(int j=0; j<ps.length; j++)
					if(factors[j]*ugly[ps[j]]==ugly[i]) ps[j]++;
		}
		System.out.format("The 1500'th ugly number is %d.\n",ugly[1500]);
	}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: