Project Euler : 91–95

• Problem 92 ( Click to read )

This is an easy problem but a naive method would be very slow. So a little optimization is needed. A catch that will reduce your work almost ten-thousand fold is the fact that the sum of square of digits below ten million can never exceed 567. To understand it, ponder on the fact that in this problem ordering of digits does not matter, that means 123 will have same sum of square of digits as 213 or 312. So the biggest number you can think of below 10 million would be 9999999 (remember that ONLY face value matters not the place value), this gives the largest ‘sum of square of digits’ and any other number will have sum below the sum of its digit’s square which is 567.

With this you have done everything, just make an array of integers below 567 and find which arrive at 1 and which at 89. having done this, start your loop from 1 till 10 million find the sum of digit and in O(1) time match that sum to pre-calculated array.

Here is my C code that gives answer in ~ 2 seconds

#include <stdio.h>
int a[570] = {0};
int main()
{
  int b[1000], j, k, r, sum;
  long int i, n;
 
  for (i=567; i>0; i -— )
  {
    if (a[i])
      continue;
    j = 1;
    n = i;
    b[0] = n;
 
    while (n!=1 && n!=89)
    {
      sum=0;
      while(n)
        r=n%10, sum += (r*r), n /= 10;
 
      b[j++] = sum;
      n=sum;
    }
    for (k=0; k<j; k++)
    {
      a[b[k]]=n;
    }
  }
  n = 0;
  for (i=1; i<10000000; i++)
  {
    j = i;
    sum = 0;
 
    while (j)
    {
      r = j%10;
      sum += (r*r);
      j /= 10;
    }
    if (a[sum] == 89)
      n++;
  }
  printf(“%ld\n”, n);
  return 0;
}

Alternate approach with Memoization

#include <stdio.h>
#define MAX 10000000
int num[MAX];
int cal(int n)
{
  int m, r, sum;
  if (num[n])
    return num[n];
  else
  {
    m = n;
    sum = 0;
 
    while (m)
    {
      r = m % 10;
      sum += (r*r);
      m /= 10;
    }
    if (!num[sum])
      num[sum] = cal(sum);
 
    num[n] = num[sum];
    return num[n];
  }
}
int main()
{
  int i, ans;
  num[1] = 1;
  num[89] = 89;
  ans = 0;
  for (i=1; i<MAX; i++)
  {
    if (cal(i) == 89)
      ans ++;
  }
  printf(“%d\n”, ans);
  return 0;
}