<Codesignal> Square Digits Sequence

Medium

Consider a sequence of numbers a0, a1, ..., an, in which an element is equal to the sum of squared digits of the previous element. The sequence ends once an element that has already been in the sequence appears again.

Given the first element a0, find the length of the sequence.

Example

• For a0 = 16, the output should be
  squareDigitsSequence(a0) = 9.

  Here's how elements of the sequence are constructed:

  • a0 = 16
  • a1 = 1^2 + 6^2 = 37
  • a2 = 3^2 + 7^2 = 58
  • a3 = 5^2 + 8^2 = 89
  • a4 = 8^2 + 9^2 = 145
  • a5 = 1^2 + 4^2 + 5^2 = 42
  • a6 = 4^2 + 2^2 = 20
  • a7 = 2^2 + 0^2 = 4
  • a8 = 4^2 = 16, which has already occurred before (a0)

  Thus, there are 9 elements in the sequence.

• For a0 = 103, the output should be
  squareDigitsSequence(a0) = 4.

  The sequence goes as follows: 103 -> 10 -> 1 -> 1, 4 elements altogether.

Input/Output

• [execution time limit] 0.5 seconds (c)

• [input] integer a0

  First element of a sequence, positive integer.

  Guaranteed constraints:
  1 ≤ a0 ≤ 10^5.

• [output] integer

[C] Syntax Tips

// Prints help message to the console
// Returns a string
char * helloWorld(char * name) {
    char * answer = malloc(strlen(name) + 8);
    printf("This prints to the console when you Run Tests");
    strcpy(answer, "Hello, ");
    strcat(answer, name);
    return answer;
}

---

Solution

int squareDigitsSequence(int a0)
{
	int count=0, temp=a0, max=a0;
	bool existed[100000]={false, };

	do
	{
		int N=0;

		existed[temp]=true;
		while(temp>0)
		{
			N+=(temp%10)*(temp%10);
			temp/=10;
		}

		temp=N;
		max=max>temp?max:temp;
	}
	while(!existed[temp]);

	for(int i=0;i<=max;i++)
		count+=existed[i];

	return count+1;
}