Project Euler #29: Distinct powers Discussions |

jxz12 10 months 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;
    }
}