We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #29: Distinct powers
  4. Discussions

Project Euler #29: Distinct powers

Problem
Submissions
Leaderboard
Discussions

Sort 41 Discussions, By:

recency

Please Login in order to post a comment

  • nightbeggar
    3 months ago+ 0 comments

    And the same code in C++.

    #include <cstdio>
    #include <vector>
    #include <set>
    using namespace std;
    
    long distinct_powers(long n) {
        long c = 0;
        vector<bool> tested(n+1, false);
        for (long a = 2; a <= n; a++) if (!tested[a]) {
            set<long> s;
            for (long _a = a*a, pw = 2; _a <= n; _a *= a, pw++) {
                tested[_a] = true;
                for (long b = 2, bxpw = b*pw; b <= n; b++, bxpw += pw)
                    if (bxpw > n)
                        s.insert(bxpw);
            }
            c += s.size() + n-1;
        }
        return c;
    }
    
    int main() {
        long n;
        scanf("%ld", &n);
        printf("%ld\n", distinct_powers(n));
        return 0;
    }
    
    0|
    Permalink
  • nightbeggar
    3 months ago+ 0 comments

    This was a bit of a rabbit hole, definitely not an "easy" task. Here's the code. The idea is for each base to iterate through its powers e.g. for 2 iterate through 4, 8, 16, ... . Create a set of exponents for each power e.g. for 8 we have 8^2=2^6, 8^3=2^9, ... and therefore exponents will be 6, 9, .. . Then merge all sets. Don't do sets for the bases though to avoid timeout.

    def distinct_terms(n: int) -> int:
        count = 0
        tested = [0]*(n+1)
        for a in range(2, n+1):
            if tested[a]: continue;
            combined = set()
            pw = 2
            while (a**pw <= n):
                tested[a**pw] = True
                s = set([b*pw for b in range(2, n+1) if b*pw > n])
                combined.update(s)
                pw += 1
            count += len(combined) + n-1            
        return count
                
    print(distinct_terms(int(input())))
    
    0|
    Permalink
  • christian_koehl1
    6 months ago+ 0 comments

    Nice challenge. For those who are struggling like I did. I counted the maximum Exponent number and then checked if b can be combined by any number below this max exponent. For example 8 = 2^3 so 8^b can be combined by 2^1*c or 2^2*d.

    int findMaxExponent(int num) {
        int root = sqrt(num);
        if(root == 1) return 1;
        
        for(int i = 2; i <= root; i++) {
            int cached_num = num;
            int expo_count = 1;
            while(cached_num % i == 0) {
                expo_count++;
                cached_num /= i;
                if(cached_num == i) {
                    return expo_count;
                }
            }
        }
        return 1;
    }
    
    0|
    Permalink
  • nc1969
    6 months ago+ 0 comments

    Easy, really? Two whole days and I haven't managed to find a O(1) solution. Used double memorization and some optimization. Final timing for N=100000 is 0.2 seconds.

    0|
    Permalink
  • tony_csoka
    2 years ago+ 0 comments

    Blimey, that was pretty tough. No way an easy problem.

    0|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy