Project Euler #29: Distinct powers Discussions |

nemrud_demir 2 years ago+ 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 1 month ago+ 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;
    }
}