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.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #29: Distinct powers
  4. Discussions

Project Euler #29: Distinct powers

  • 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;
    }
}