Project Euler #29: Distinct powers

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