# Project Euler #29: Distinct powers

# Project Euler #29: Distinct powers

Abdelrahman_Atia + 4 comments How is this easy problem ???!!!!

laizenan + 0 comments Agree, it should have been moved to mid or even hard section!

Crafter_Artisan + 0 comments [deleted]kedavamaru + 1 comment Yeah it has its trick, it took me some time but I finally solved it.

qayum_khan_usa + 0 comments Currently, Project Euler+ is a live competition. So HackerRank forbids the publishing of code, either as a solution or in asking for debugging help. This is not a "practice" challenge:

https://www.hackerrank.com/faq/sharing-codeI will state that my

**11-line Python3 solution**does involve`set`

s but neither`float`

s (except one square-root, so**no logarithms**) nor`long int`

s (technically Python doesn't need this data type, but I mean no integer beyond`100_000`

). I did eventually pass*Testcase 10*by eliminating all floating-point arithmetic except that one square-root. As usual in Project Euler+, high-performance code does involve a cache/memoization, but otherwise here neither recursion nor dynamic programming.*Just do some examples by hand and reflect deeply on your thought process — this forces one to avoid excessive bruteforce!*

nemrud_demir + 1 comment Wrong answer for the last 3 cases and I have no idea why... I get 9981236306 for n=100000

Edit: My solution worked but it took to much memory (about 600MB for n=100000 [Limit is 512MB]) I noticed it after tc18 got a runtime error randomly

I optimized the code and all testcases were accepted

jxz12 + 0 comments I had the same issue in C#, but found that the memory limit is even stricter (~300mb). I ended up writing this class to store bools instead, hopefully someone will find it helpful:

public class BoolMatrix { private Dictionary<int, uint[]> matrix; private int numCells; public BoolMatrix(int size) { // each 'cell' is effectively used as an array for 32 bools numCells = (int)Math.Ceiling((double)size / 32); matrix = new Dictionary<int, uint[]>(); } public void SetTrue(int row, int col) { row -= 1; col -= 1; if (!matrix.ContainsKey(row)) { matrix[row] = new uint[numCells]; } matrix[row][col/32] |= (uint)(1 << (col%32)); } public long CountTrues() { long trues = 0; foreach (var row in matrix.Values) { for (int i=0; i<row.Length; i++) { trues += CountBits(row[i]); } } return trues; } // Kernighan's algorithm private int CountBits(uint n) { int count = 0; while (n > 0) { n &= n-1; count += 1; } return count; } }

kormak + 0 comments Well this problem was hell on earth to pass all the cases.

HINT: When can a number have coinciding powers with other numbers?

If a number can have coinciding numbers with other numbers do we need to compute the power or can we a get a shortcut through the exponent?

If a number cannot have coinciding powers with another number, how many distinct powers does this number provide?

EdsonLin + 1 comment only can't pass the 10th,wa =.=

Wdbceg + 1 comment I can't pass 10th as well previously. I think it's beacuse of the inaccuracy of Math.log and double, if you are using log(max)/log(i)

n_sefa_dolunay + 0 comments "logl" solved this problem for c++

ayush002 + 1 comment My solution in python-----

n=int(input()) k=1 while(pow(2,k)<=n): k+=1 last=k lists={} for i in range(1,last): lists[i]=[] for j in range(2,n+1): lists[i].append(j*i) if(i!=1): temp=list(set().union(lists[i-1],lists[i])) lists[i]=temp check=[] for i in range(2,n+1): check.append(0) ans=0 for i in range(2,n+1): if(check[i-2]==0): check[i-2]=1 j=i*i while(j<=n): check[j-2]=1 j=j*i k=1 while(pow(i,k)<=n): k+=1 last=k ans+=len(lists[k-1]) print(ans)

guts123 + 0 comments what are the intitution behind this can you explain?

Sort 36 Discussions, By:

Please Login in order to post a comment