Hi rock,
I simply add as many factors as will fit within a certain range.
You can supply any range you like, as long as there are at least n (in this case 1500) ugly numbers in the range.
By calculating the entire 64-bit unsigned range, I found the following amount of ugly numbers:
Code: Select all
RANGE g_range[21] =
{
1, 1,
10, 9,
100, 34,
1000, 86,
10000, 175,
100000, 313,
1000000, 507,
10000000, 768,
100000000, 1105,
1000000000, 1530,
10000000000, 2053,
100000000000, 2683,
1000000000000, 3429,
10000000000000, 4301,
100000000000000, 5310,
1000000000000000, 6466,
10000000000000000, 7780,
100000000000000000, 9259,
1000000000000000000, 10941,
10000000000000000000, 13790,
18446744073709551615, 41853
};
As you can see, we only need to check the range [0, 1000000000].
Basically, this is what you do:
[cpp]
// Calculate the maximum powers for 2, 3, and 5
u8MaxPower2 = (uint8)(log((double)u64Max) / log(2.0));
u8MaxPower3 = (uint8)(log((double)u64Max) / log(3.0));
u8MaxPower5 = (uint8)(log((double)u64Max) / log(5.0));
// Keep adding factors of 5 while we are within the range
for(uint8 u8Factor5=0;u8Factor5<=u8MaxPower5;u8Factor5++)
{
// Keep adding factors of 3 while we are within the range
for(uint8 u8Factor3=0;u8Factor3<=u8MaxPower3;u8Factor3++)
{
// Keep adding factors of 2 while we are within the range
for(uint8 u8Factor2=0;u8Factor2<=u8MaxPower2;u8Factor2++)
{
// Is the ugly number within the range?
pu64Ugly[u16TotUgly] = g_pu64Pow2[u8Factor2] * g_pu64Pow3[u8Factor3] * g_pu64Pow5[u8Factor5];
if(pu64Ugly[u16TotUgly] <= u64Max)
u16TotUgly++;
else
break;
}
}
}
[/cpp]
My complete program is as follows:
[cpp]
// @JUDGE_ID: 33444KK 136 C++
//
// 136_UglyNumbers: Find the nth number which is only divisible by 2,3, or 5
//
#include <cstdio>
#include <cmath>
// The base types
#ifdef WIN32
typedef __int8 int8;
typedef __int16 int16;
typedef __int32 int32;
typedef __int64 int64;
typedef unsigned __int8 uint8;
typedef unsigned __int16 uint16;
typedef unsigned __int32 uint32;
typedef unsigned __int64 uint64;
#else
typedef char int8;
typedef short int16;
typedef long int32;
typedef long long int int64;
typedef unsigned char uint8;
typedef unsigned short uint16;
typedef unsigned long uint32;
typedef unsigned long long int uint64;
#endif
// These macros safely delete (an array of) objects
#define SAFE_DELETE(pObj) { if(pObj) { delete pObj; pObj = NULL; } }
#define SAFE_DELETE_ARRAY(pArr) { if(pArr) { delete[] pArr; pArr = NULL; } }
// The 2^n table
uint64 g_pu64Pow2[64] =
{
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768,
65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216,
33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648,
4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472,
274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104,
8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328,
281474976710656, 562949953421312, 1125899906842624, 2251799813685248,
4503599627370496, 9007199254740992, 18014398509481984, 36028797018963968,
72057594037927936, 144115188075855872, 288230376151711744, 576460752303423488,
1152921504606846976, 2305843009213693952, 4611686018427387904, 9223372036854775808
};
// The 3^n table
uint64 g_pu64Pow3[42] =
{
1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323,
4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203,
31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987,
22876792454961, 68630377364883, 205891132094649, 617673396283947, 1853020188851841,
5559060566555523, 16677181699666569, 50031545098999707, 150094635296999121,
450283905890997363, 1350851717672992089, 4052555153018976267, 12157665459056928801,
18026252303461234787
};
// The 5^n table
uint64 g_pu64Pow5[28] =
{
1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625, 48828125, 244140625,
1220703125, 6103515625, 30517578125, 152587890625, 762939453125, 3814697265625,
19073486328125, 95367431640625, 476837158203125, 2384185791015625, 11920928955078125,
59604644775390625, 298023223876953125, 1490116119384765625, 7450580596923828125
};
struct RANGE
{
uint64 u64Max; // The highest possible ugly number
uint16 u16TotCount; // The amount of ugly numbers in the range [1,u64Max]
};
// The amount of ugly numbers in the range [1,u64Max];
RANGE g_range[21] =
{
1, 1,
10, 9,
100, 34,
1000, 86,
10000, 175,
100000, 313,
1000000, 507,
10000000, 768,
100000000, 1105,
1000000000, 1530,
10000000000, 2053,
100000000000, 2683,
1000000000000, 3429,
10000000000000, 4301,
100000000000000, 5310,
1000000000000000, 6466,
10000000000000000, 7780,
100000000000000000, 9259,
1000000000000000000, 10941,
10000000000000000000, 13790,
18446744073709551615, 41853
};
// The ugly number
#define NTH_UGLY_NUMBER 1500
// The function prototypes
void GetUglyNumbers(uint64 *pu64Ugly, uint64 u64Max);
void QuickSort(uint64 *pu64Ugly, int32 i32LeftOrg, int32 i32RightOrg);
//-------------------------------------------------------------
// F U N C T I O N S
//-------------------------------------------------------------
// This function is the entrance of the app
int main()
{
// Get the upper limit of the ugly number
for(uint8 u8=0;u8<21;u8++)
{
// Are there enough ugly numbers?
if(g_range[u8].u16TotCount > NTH_UGLY_NUMBER)
{
uint64 *pu64UglyNumbers;
// Allocate a new buffer to hold the ugly numbers
pu64UglyNumbers = new uint64[g_range[u8].u16TotCount+1];
// Find all the ugly numbers in the range [1,N]
GetUglyNumbers(pu64UglyNumbers, g_range[u8].u64Max);
// Show the requested number
printf("The 1500'th ugly number is %I64u.", pu64UglyNumbers[NTH_UGLY_NUMBER-1]);
// Free the resources
SAFE_DELETE_ARRAY(pu64UglyNumbers);
break;
}
}
return 0;
}
//-------------------------------------------------------------
// This function locates all the ugly numbers in the range [u64Min,u64Max]
void GetUglyNumbers(uint64 *pu64Ugly, uint64 u64Max)
{
uint8 u8MaxPower2, u8MaxPower3, u8MaxPower5;
uint16 u16TotUgly = 0;
// Calculate the maximum powers for 2, 3, and 5
u8MaxPower2 = (uint8)(log((double)u64Max) / log(2.0));
u8MaxPower3 = (uint8)(log((double)u64Max) / log(3.0));
u8MaxPower5 = (uint8)(log((double)u64Max) / log(5.0));
// Keep adding factors of 5 while we are within the range
for(uint8 u8Factor5=0;u8Factor5<=u8MaxPower5;u8Factor5++)
{
// Keep adding factors of 3 while we are within the range
for(uint8 u8Factor3=0;u8Factor3<=u8MaxPower3;u8Factor3++)
{
// Keep adding factors of 2 while we are within the range
for(uint8 u8Factor2=0;u8Factor2<=u8MaxPower2;u8Factor2++)
{
// Is the ugly number within the range?
pu64Ugly[u16TotUgly] = g_pu64Pow2[u8Factor2] * g_pu64Pow3[u8Factor3] * g_pu64Pow5[u8Factor5];
if(pu64Ugly[u16TotUgly] <= u64Max)
u16TotUgly++;
else
break;
}
}
}
// Sort the values
QuickSort(pu64Ugly, 0, u16TotUgly-1);
}
//-------------------------------------------------------------
// This function uses the quick sort algorithm to sort elements
void QuickSort(uint64 *pu64Ugly, int32 i32LeftOrg, int32 i32RightOrg)
{
int32 i32Left, i32Right;
uint64 u64Mid;
// Get the left and right positions
i32Left = i32LeftOrg;
i32Right = i32RightOrg;
// Get the middle element (hopefully also somewhere in the middle value-wise)
u64Mid = pu64Ugly[(i32Left + i32Right) / 2];
// Let the left and right positions walk towards each other until they pass each other
while(i32Right >= i32LeftOrg && i32Left <= i32RightOrg)
{
// Find the left-most element which is too high to be on the left side of the middle element
while(u64Mid > pu64Ugly[i32Left]) i32Left++;
// Find the right-most element which is too low to be on the right side of the middle element
while(pu64Ugly[i32Right] > u64Mid) i32Right--;
// Have the left and right pointer not yet passed each other?
if(i32Left <= i32Right)
{
// Are the left and right element different elements?
if(i32Left < i32Right)
{
uint64 u64Temp;
// Swap the elements which are on the wrong side of the middle element
u64Temp = pu64Ugly[i32Left];
pu64Ugly[i32Left] = pu64Ugly[i32Right];
pu64Ugly[i32Right] = u64Temp;
}
// Step towards each other
i32Left++;
i32Right--;
}
else break;
}
// Have we not yet walked all the way from the right element to the left element?
if(i32LeftOrg < i32Right) QuickSort(pu64Ugly, i32LeftOrg, i32Right);
// Have we not yet walked all the way from the left element to the right element?
if(i32Left < i32RightOrg) QuickSort(pu64Ugly, i32Left, i32RightOrg);
}[/cpp]