A better solution, easier to understand


#1

string Solution::multiple(int A)
{
string ans = “”;
int onemodA = 1 % A;
int tenmodA = 10 % A;
if(onemodA == 0)
{
return(“1”);
}
if(A == 0)
{
return(“0”);
}
int states[A];
memset(states, 0, A * sizeof(int));
queue q;
q.push(onemodA);
states[onemodA] = onemodA;
while(1)
{
int temp = q.front();
q.pop();
int modleft = (temp * tenmodA) % A;
if(modleft == 0)
{
states[0] = -1 * temp;
break;
}
if(states[modleft] == 0)
{
states[modleft] = -1 * temp;
q.push(modleft);
}
int modright = (modleft + onemodA) % A;
if(modright == 0)
{
states[0] = temp;
break;
}
if(states[modright] == 0)
{
states[modright] = temp;
q.push(modright);
}
}
int state = 0;
while(state != onemodA)
{
if(states[state] > 0)
{
ans = “1” + ans;
state = states[state];
}
else
{
ans = “0” + ans;
state = -1 * states[state];
}
}
return(“1” + ans);
}


#2

If only it was easier to read