This guy had explained it well


#1

Just instead of dp of string like he had used , use a dp which contains the parent node and the extra character (‘0’/‘1’) that was appended on it from the parent.

"
string multiple_Optimized(int A)
{
if(A==1)
return “1”;
// First represent the current charater that it obtain from its parent
// Second is the parent (initialized with -1 to check all nodes are visited once)
vector <pair<char,int>> dp(A,{‘1’,-1});
dp[1].second=1;

    queue <int> Q;
	Q.push(1);
	while(!Q.empty())
	{
		int r = Q.front();
		Q.pop();
		if(r==0){

			string str;
			while(r!= 1)
			{
				str+=dp[r].first;
				r=dp[r].second;
			}
			str+='1';
			reverse(str.begin(),str.end());
			return str;
			
		}
		for(int digit : {0,1})
		{
			int new_r = (r*10 + digit	)% A;
			if(dp[new_r].second == -1)
			{
				dp[new_r].second = r;
				dp[new_r].first  = char('0' + digit);
				Q.push(new_r);
			}
		}
	}

    return ""; 
}

"