-
Notifications
You must be signed in to change notification settings - Fork 35
/
Copy patheuler-0029.cpp
151 lines (140 loc) · 6.69 KB
/
euler-0029.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
// ////////////////////////////////////////////////////////
// # Title
// Distinct powers
//
// # URL
// https://projecteuler.net/problem=29
// http://euler.stephan-brumme.com/29/
//
// # Problem
// Consider all integer combinations of `a^b` for `2 <= a <= 5` and `2 <= b <= 5`:
//
// `2^2= 4`, `2^3= 8`, `2^4= 16`, `2^5= 32`
// `3^2= 9`, `3^3= 27`, `3^4= 81`, `3^5= 243`
// `4^2=16`, `4^3= 64`, `4^4=256`, `4^5=1024`
// `5^2=25`, `5^3=125`, `5^4=625`, `5^5=3125`
//
// If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:
//
// 4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
//
// How many distinct terms are in the sequence generated by ab for `2 <= a <= 100` and `2 <= b <= 100`?
//
// # Solved by
// Stephan Brumme
// February 2017
//
// # Algorithm
// The core problem is: find all `x^y` where also an `a^b` exists with `x>a` and `x <= limit` (a "collision").
// The only collision in the problem's example is `x^y=4^2=16` and `a^b=2^4=2^4=16`.
// My variable ''repeated'' counts all numbers that appear repeatedly (such as `16`).
// The final result will be `(limit-1)^2 - repeated` (for the example we found that `repeated=1` and therefore `(5-1)^2 - 1 = 15`).
//
// The rest of this algorithm is all about an efficient way to find the value of `repeated`.
//
// __Note:__ we have `limit=5` in the example but we need to solve for `limit=100` (or `limit=100000` in the modified Hackerrank problem).
//
// Because of `4=2^2` we know that `4^y=2^{2y}`: all powers with base `4` can be rewritten as `4^2=2^{2*2}=2^4`, `4^3=2^{2*3}=2^6`, `4^4=2^{2*4}=2^8` and `4^5=2^{2*5}=2^{10}`.
// Therefore when we convert all powers of `4` to powers of `2` we use those exponents: ''2,3,4,5'' (for `a=2`) and ''4,6,8,10'' (for `x=4` ==> `a=2^2`).
// Obviously ''4'' is found in both sets. That's our collision.
//
// The first step in my program is to find all exponents if we reduce all numbers `x` to their "parent" `a^b`:
// 1. we know for certain that all numbers from `2` to `limit` will be used: ''2,3,4,5''
// 2. if `x=a^2` is a valid base (that means `x <= limit`), then ''2*2,2*3,2*4,2*5'' will be used for base `a`, too.
// 3. if `x=a^3` is a valid base then ''3*2,3*3,3*4,3*5'' will be used for base `a`, too.
// 4. if `x=a^4` is a valid base then ''4*2,4*3,4*4,4*5'' will be used for base `a`, too.
// 5. and so on ...
//
// My container ''minExponent'' records which exponents could be used. If there are multiple combinations, then the lowest is stored.
// I hope an example makes things a bit clearer:
// 1. insert ''1'' at positions ''2,3,4,5''
// 2. insert ''2'' at positions ''6,8,10'' ==> but not at position 4 because that one is already occupied
// 3. we can stop because there is no other base `x=2^3 <= limit`
//
// ''minExponent'' contains ''2 ==> 1, 3 ==> 1, 4 ==> 1, 5 ==> 1, 6 ==> 2, 8 ==> 2, 10 ==> 2''
// An ''std::vector'' doesn't have gaps and starts at 0, that's why I there are some unused entries, too, filled with zero:
// ''minExponent = { 0, 0, 1, 1, 1, 1, 2, 0, 2, 0, 2 }''
//
// The "highest" collision with base `2^b=x^y` can be found for `2^b=64^y=2^{8y}` (next power of 2 is 128, which is larger than 100).
// For the modified Hackerrank problem, this "highest" collision with base `2^b=x^y` can be found for `x^y=65536^y=2^{16y}` (limit is 100000 instead of 100).
// That's why ''MaxBasePower = 16''.
//
// My container ''base'' is zero for every ''base[x]'' where there no `a^b=x` exists. The data structure is incrementally updated and initially all entries are zero.
// If we encounter such a ''base[x]=0'' then we immediately fill ''base[x*x]=x'' and ''base[x*x*x]=x'' and ''base[x*x*x*x]=x'' ...
// because ''x*x'', ''x*x*x'', ... will collide with ''x''.
// In the example, for ''x=2'' we'll find that ''base[2]=0'' and hence fill ''base[2*2]=2''.
// If ''base[x] == 0'' then collisions with smaller x are impossible.
//
// If ''base[x] != 0'' then ''x'' has a "parent" such that `x=base[x]^exponent`. Collisions are possible.
// We scan through ''minExponent'' and count all collisions (in ''repeated''):
// Due to `x^y = base[x]^{y*exponent}` all elements ''minExponent[y*exponent]'' have to be checked if that entry was
// already used by some other ''x''.
//
// # Alternative
// The original problem can be solved by brute-force if your language supports big integers.
// I haven't tried it but maybe you can store `log{a^b}` in a ''std::set'', too.
//
// # Hackerrank
// The higher limit of 100000 instead of 100 forced me to come up with my slightly more complex but much faster solution.
// The result exceeds 32 bits (for limit close to 100000), that's why I introduced the ''all'' variable as ''unsigned long long''.
#include <iostream>
#include <vector>
int main()
{
// I called it "limit" in the explanation
unsigned int maxExponent;
std::cin >> maxExponent;
// 2^17 > 10^5 (max. input)
const unsigned int MaxBasePower = 16;
// if a^b = base^(exponent*basePower)
// then b = (1..n) but exponent*basePower = (basePower, 2*basePower, 3*basePower, ..., n*basePower)
// store for each product exponent*basePower the smallest basePower
std::vector<unsigned int> minExponent((maxExponent+1)*MaxBasePower);
for (unsigned int i = 1; i <= MaxBasePower; i++)
for (unsigned int j = 1; j <= maxExponent; j++)
if (minExponent[i*j] == 0)
minExponent[i*j] = i;
// all "a" which can be composed as base^exponent, stored as [a] => [base]
std::vector<unsigned int> base(maxExponent + 1, 0);
// how often numbers were used multiple times (those are the collisions we are looking for)
unsigned int repeated = 0;
// analyze all bases
for (unsigned int x = 2; x <= maxExponent; x++) // maximum base is maxExponent, too
{
// is x = parent^exponent ?
auto parent = base[x];
if (parent == 0) // no
{
// find all future children where "x" is the parent
auto power = x * x;
// [x^2] = [x^3] = [x^4] = ... = x
while (power <= maxExponent)
{
base[power] = x;
power *= x;
}
// no x=a^b possible, "repeated" remains unchanged
continue;
}
// we have a parent, find exponent such that a = parent^exponent
unsigned int exponent = 0;
auto reduce = x;
while (reduce > 1)
{
reduce /= parent;
exponent++;
}
// analyze all pairs, and count all numbers we saw before (repeated++)
for (unsigned int y = 2; y <= maxExponent; y++)
{
// that exponent was already used ?
if (minExponent[y * exponent] < exponent)
repeated++;
}
}
// there are (maxExponent-1)^2 combinations, subtract all duplicates
unsigned long long all = maxExponent - 1;
auto result = all*all - repeated;
std::cout << result << std::endl;
return 0;
}