On the site, my attention was captured by this puzzle involving "ugly" numbers.
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.
This isn't a particular hard puzzle if you brute force it. All you have to do is write an algorithm to determine whether a particular number is ugly or not, sort of like this:
while (num % 2 == 0) num /= 2;
while (num % 3 == 0) num /= 3;
while (num % 5 == 0) num /= 5;
if (num == 1) return true;
Then you can just loop through as many numbers as it takes, incrementing a counter as you find ugly numbers, until you reach 1500 numbers.
The problem with this approach is that there is a time limit of three seconds. The brute force approach requires you to do an increasingly long operation (dividing repeatedly to find the prime factors) on a series of numbers which turns out to be very large (I won't spoil it, but the answer is just short of one trillion). Early numbers are computer quickly; then it slows down so finding the 1500th number may take several minutes.
I confess I cheated to solve this puzzle. I came up with one other wrong approach after trying the brute force method, then went googling for discussions of this puzzle. As I hoped, I did find a protracted argument about the right way to solve it. One guy hit on a really clever solution, based on a data structure which I haven't used for years. It took me a few tries to implement, but it was very satisfying in the end.
I guess I could feel bad for "cheating," but I don't. I came close to finding the right answer, but really, if you want an optimal answer to a well defined puzzle then there's no harm in hunting around to see if someone did it better than you. Professionally, implementing a GREAT solution that you looked up is preferable to implementing a mediocre solution that you got with only the sweat of your brow. You can learn new tricks from other people that you'll have in your toolbox for next time.
As a tangent, I take the same approach to strategy games. I like to take my time and learn the rules of a game on my own, and I would scorn to look at a strategy guide during that period. However, there comes a point where you have a basic understanding of the rules and can improve much faster by considering input from others who have already mastered the game.
Anyway, more on the wrong approaches and the right one later.
Looking forward to your next article with the right approaches. Without thinking much but using good old number sense, you can make the 2 and 5 checks with simple checks of the last digit of the integer. If last digit is in {0,2,4,5,6,8} then is is divisible by 2 or 5. For the 3 check, if the sum of the digits is divisible by 3, then the integer is divisible by 3. Not sure if these are faster when implemented by computers, but certainly they are when implemented by humans.
ReplyDeleteSadly, it's not even that simple. Sure, you can find out if the number is divisible by 2, 3, and 5, but even then, it may not be ugly. For instance: 2*2*2*3*3*3*5*5*5*7 is not ugly because it has an illegal factor of 7 in it.
ReplyDeleteThe brute force method looks at finished numbers. If there is a way to make the program do the calculations itself and repeat that 1500 times that would be faster. The problem is coming up with a calculation you could properly increment, that would include all ugly numbers.
ReplyDeleteAt least that is the idea off the top of my head.
Dang it, see, that's why it takes me 3 revisions before I send work emails :-)
ReplyDeleteyeah but i use this algorithm u said
ReplyDeletebut i get time limit exceeded as i print in the screen 1500 number it take long time 3.000 ms
but the required is 1.000 ms .
The required time is posted as 3.000 seconds. If your development environment can't display numbers in the required amount of time then maybe you should consider outputting them to a file instead, then you can inspect the result to make sure it is correct.
ReplyDeleteWe can model this recursively, each recursive level tries to deal with one of the prime factors.
ReplyDeletefunction myfunc(idx, ugly)
if idx == 3
add ugly into collection of ugly numbers
return
end if
## At this stage, there are two paths to take
## We can keep on using the current factor.
## We can also start using the larger factor.
## We need to explore both paths.
if ugly * f[idx] <= MAX
myfunc(idx, ugly * f[idx])
end if
myfunc(idx + 1, ugly)
end function
Note: MAX is the upper bound of the ugly number value. f[] = { 2, 3, 5 }
We can start the recursive call by doing myfunc(0, 1). This will give the collection of ugly numbers from in range [1 .. MAX].
Taking the k-th element out of the sorted collection of ugly numbers should be straightforward then.
If there is a way to make the program do the calculations itself
ReplyDeletespace strategy games.