Problem
Method 1 - Brute force
Loop for all positive integers until ugly number count is smaller than n, if an integer is ugly than increment ugly number count.
To check if a number is ugly, divide the number by greatest divisible powers of 2, 3 and 5, if the number becomes 1 then it is an ugly number otherwise not.
For example, let us see how to check for 300 is ugly or not. Greatest divisible power of 2 is 4, after dividing 300 by 4 we get 75. Greatest divisible power of 3 is 3, after dividing 75 by 3 we get 25. Greatest divisible power of 5 is 25, after dividing 25 by 25 we get 1. Since we get 1 finally, 300 is ugly number.
This method is not time efficient as it checks for all integers until ugly number count becomes n, but space complexity of this method is O(1)
Method 2 - Using dynamic programming
Suppose N = 50
Here is the code in java
References
http://www.geeksforgeeks.org/ugly-numbers/
http://stackoverflow.com/questions/4600048/nth-ugly-number
http://tianrunhe.wordpress.com/2012/04/03/find-the-kth-number-with-prime-factors-3-5-and-7/
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... shows the first 11 ugly numbers. ...By convention, 1 is included. Write a program to find and print the 1500'th ugly number.Solution
Method 1 - Brute force
Loop for all positive integers until ugly number count is smaller than n, if an integer is ugly than increment ugly number count.
To check if a number is ugly, divide the number by greatest divisible powers of 2, 3 and 5, if the number becomes 1 then it is an ugly number otherwise not.
For example, let us see how to check for 300 is ugly or not. Greatest divisible power of 2 is 4, after dividing 300 by 4 we get 75. Greatest divisible power of 3 is 3, after dividing 75 by 3 we get 25. Greatest divisible power of 5 is 25, after dividing 25 by 25 we get 1. Since we get 1 finally, 300 is ugly number.
private static int maxDivide(int a, int b) { while (a%b == 0) a = a/b; return a; } private static int isUgly(int no) { no = maxDivide(no, 2); no = maxDivide(no, 3); no = maxDivide(no, 5); return (no == 1)? 1 : 0; } /* Function to get the nth ugly number*/ public static int getNthUglyNo(int n) { int i = 1; int count = 1; /* ugly number count */ while (n > count) { i++; if (isUgly(i)) count++; } return i; }
This method is not time efficient as it checks for all integers until ugly number count becomes n, but space complexity of this method is O(1)
Method 2 - Using dynamic programming
1 Declare an array for ugly numbers: ugly[150] 2 Initialize first ugly no: ugly[0] = 1 3 Initialize three array index variables i2, i3, i5 to point to 1st element of the ugly array: i2 = i3 = i5 =0; 4 Initialize 3 choices for the next ugly no: next_mulitple_of_2 = ugly[i2]*2; next_mulitple_of_3 = ugly[i3]*3 next_mulitple_of_5 = ugly[i5]*5; 5 Now go in a loop to fill all ugly numbers till 150: For (i = 1; i < 150; i++ ) { /* These small steps are not optimized for good readability. Will optimize them in C program */ next_ugly_no = Min(next_mulitple_of_2, next_mulitple_of_3, next_mulitple_of_5); if (next_ugly_no == next_mulitple_of_2) { i2 = i2 + 1; next_mulitple_of_2 = ugly[i2]*2; } if (next_ugly_no == next_mulitple_of_3) { i3 = i3 + 1; next_mulitple_of_3 = ugly[i3]*3; } if (next_ugly_no == next_mulitple_of_5) { i5 = i5 + 1; next_mulitple_of_5 = ugly[i5]*5; } ugly[i] = next_ugly_no }/* end of for loop */ 6.return next_ugly_noExample
Suppose N = 50
initialize ugly[] = | 1 | i2 = i3 = i5 = 0; First iteration ugly[1] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5) = Min(2, 3, 5) = 2 ugly[] = | 1 | 2 | i2 = 1, i3 = i5 = 0 (i2 got incremented ) Second iteration ugly[2] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5) = Min(4, 3, 5) = 3 ugly[] = | 1 | 2 | 3 | i2 = 1, i3 = 1, i5 = 0 (i3 got incremented ) Third iteration ugly[3] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5) = Min(4, 6, 5) = 4 ugly[] = | 1 | 2 | 3 | 4 | i2 = 2, i3 = 1, i5 = 0 (i2 got incremented ) Fourth iteration ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5) = Min(6, 6, 5) = 5 ugly[] = | 1 | 2 | 3 | 4 | 5 | i2 = 2, i3 = 1, i5 = 1 (i5 got incremented ) Fifth iteration ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5) = Min(6, 6, 10) = 6 ugly[] = | 1 | 2 | 3 | 4 | 5 | 6 | i2 = 3, i3 = 2, i5 = 1 (i2 and i3 got incremented ) Will continue same way till I < 150
Here is the code in java
public static int getKthMagicNumber(int k) { if (k <= 0) return 0; int val = 1; Queue<Integer> Q2 = new LinkedList<Integer>(); Queue<Integer> Q3 = new LinkedList<Integer>(); Queue<Integer> Q5 = new LinkedList<Integer>(); Q2.add(2); Q3.add(3); Q5.add(5); for (--k; k > 0; --k) { // We’ve done one iteration already. val = Math.min(Q2.peek().intValue(), Math.min(Q3.peek().intValue(), Q5.peek().intValue())); if (val == Q5.peek()) { Q5.remove(); } else { if (val == Q3.peek()) { Q3.remove(); } else { // must be from Q2 Q2.remove(); Q2.add(val * 2); } Q3.add(val * 3); } Q5.add(val * 5); } return val; }
References
http://www.geeksforgeeks.org/ugly-numbers/
http://stackoverflow.com/questions/4600048/nth-ugly-number
http://tianrunhe.wordpress.com/2012/04/03/find-the-kth-number-with-prime-factors-3-5-and-7/
0 comments:
Post a Comment