divisionDp.cpp

#include<bits/stdc++.h>
using namespace std;

string ss;
stack<int>result;
vector<int> arr;
int n, k;
int dp[1123][123];
int stop = 0;         /* To stop the search for further solutions */
 

/* Recursive function to get a solution */
int solve(int i, int j)
{
  int remainder, op_retain, op_delete;

  /* If we are out of digits or we already have a solution */
  if(i>=n||stop)
    return 0;

  /* When we have already computed the solution for this state */
  if(dp[i][j]!=-1)
    return dp[i][j];
 
 /* Computing the remainder if we include current digit */ 
  remainder = (j*10 + arr[i]) % k;
 
 /* If remainder is 0 we found the solution, we can return true */ 
  if(remainder == 0)
  {
    stop = 1;
    result.push(arr[i]);
    dp[i][j]=1;
    return 1;
  }
 
  /* Our 2 choices, retain or delete the current digit */
  op_retain = solve(i+1, remainder);
  op_delete = solve(i+1,j);
  
  /* If retention led to a true state, include that digit in our result */
  if(op_retain)
     result.push(arr[i]);
  
  /* Storing whether it was possible to get a candidate from this state */
  dp[i][j] = op_retain||op_delete;
  
  return dp[i][j];
}

int main() {

  /* Taking the inputs */
  cin >>ss;
  cin>>k;
  n = ss.length();

  /* Converting a String input to an array of intergers */
  for(auto x:ss)
    arr.push_back(x -'0');
 
  /* Initialising the dp array */ 
  for(int i=0;i<n;i++)
    for(int j=0;j<k;j++)
      dp[i][j]=-1;
    
  /* Recursive call from state S[0, 0] */
  int ans = solve(0,0);
 
  /* If we were able to find a solution, printing it, else printing "NO" */
  if(ans)
  {
    while(!result.empty())
    {
      cout<<result.top();
      result.pop();
    }
    cout<<endl;
  }
  else
    cout<<"NO"<<endl;
 
  return 0;
}