Labels

Project Euler #49: Prime permutations (C++)

Question
The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.
There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.
What 12-digit number do you form by concatenating the three terms in this sequence?

Answer : 296962999629

Hacker Rank Problem

Solution 
  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
#include <set>
#include <map>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <complex>

unsigned long long fingerprint(unsigned int x) {
    unsigned long long result = 0;
    while(x > 0) {
        auto digit = x % 10;
        x /= 10;
        unsigned long long pos = 1;
        for(unsigned int i = 1; i <= digit; i++) {
            pos *= 10;
        }
        result += pos;
    }
    return result;
}

int main() {
    unsigned int N;
    unsigned int K;
    std::cin >> N >> K;
    std::set<unsigned int> primes;
    primes.insert(2);
    for(unsigned int i = 3; i < std::pow(10, 6); i += 2) {
        bool isPrime = true;
        for(auto p : primes) {
            if((p * p) > i) {
                break;
            }
            if((i % p) == 0) {
                isPrime = false;
                break;
            }
        }
        if(isPrime) {
            primes.insert(i);
        }
    }
    std::map<unsigned long long, unsigned int> PrintDatas;
    for(auto p : primes) {
        PrintDatas[fingerprint(p)]++;
    }
    std::map<unsigned int, std::set<std::string>> result;
    for(auto p : primes) {
        if(p < 1000) {
            continue;
        }
        if(p >= N) {
            break;
        }
        if(PrintDatas[fingerprint(p)] < 3) {
            continue;
        }
        std::string digits = std::to_string(p);
        std::sort(digits.begin(), digits.end());
        std::set<unsigned int> candidates;
        do {
            if(digits[0] == '0') {
                continue;
            }
            unsigned int permuted = std::stoi(digits);
            if(primes.count(permuted) == 0) {
                continue;
            }
            if(permuted < p) {
                break;
            }
            candidates.insert(permuted);
        } while(std::next_permutation(digits.begin(), digits.end()));
        if(candidates.size() < K) {
            continue;
        }
        std::map<unsigned int, std::set<unsigned int>> differences;
        for(auto bigger : candidates) {
            for(auto smaller : candidates) {
                if(smaller >= bigger) {
                    break;
                }
                differences[bigger - smaller].insert(bigger);
                differences[bigger - smaller].insert(smaller);
            }
        }
        for(auto d : differences) {
            if(d.second.size() < K) {
                continue;
            }
            auto diff = d.first;
            auto all = d.second;
            for(auto start : all) {
                if(start >= N) {
                    continue;
                }
                unsigned int followers = 0;
                unsigned int next = start + diff;
                while(all.count(next) != 0) {
                    followers++;
                    next += diff;
                }
                if(followers >= K - 1) {
                    auto next = start + diff;
                    std::string s = std::to_string(start);
                    for(unsigned int printMe = 1; printMe < K; printMe++) {
                        s += std::to_string(next);
                        next += diff;
                    }
                    result[s.size()].insert(s);
                }
            }
        }
    }
    for(auto length : result) {
        for(auto x : length.second) {
            std::cout << x << std::endl;
        }
    }
    return 0;
}
Labels:

Comments

Post a Comment

Popular Posts