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]