Smallest multiple of N formed using the given set of digits | C ++ implementation of the approach ; Function to return the required number ; Initialize both vectors with their initial values ; Sort the vector of digits ; Initialize the queue ; If modulus value is not present in the queue ; Compute digits modulus given number and update the queue and vectors ; While queue is not empty ; Remove the first element of the queue ; Compute new modulus values by using old queue values and each digit of the set ; If value is not present in the queue ; If required condition can 't be satisfied ; Initialize new vector ; Constructing the solution by backtracking ; Reverse the vector ; Return the required number ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findSmallestNumber ( vector < int > & arr , int n ) { vector < int > dp ( n , numeric_limits < int > :: max ( ) - 5 ) ; vector < pair < int , int > > result ( n , make_pair ( -1 , 0 ) ) ; sort ( arr . begin ( ) , arr . end ( ) ) ; queue < int > q ; for ( auto i : arr ) { if ( i != 0 ) { if ( dp [ i % n ] > 1e9 ) { q . push ( i % n ) ; dp [ i % n ] = 1 ; result [ i % n ] = { -1 , i } ; } } } while ( ! q . empty ( ) ) { int u = q . front ( ) ; q . pop ( ) ; for ( auto i : arr ) { int v = ( u * 10 + i ) % n ; if ( dp [ u ] + 1 < dp [ v ] ) { dp [ v ] = dp [ u ] + 1 ; q . push ( v ) ; result [ v ] = { u , i } ; } } } if ( dp [ 0 ] > 1e9 ) return -1 ; else { vector < int > ans ; int u = 0 ; while ( u != -1 ) { ans . push_back ( result [ u ] . second ) ; u = result [ u ] . first ; } reverse ( ans . begin ( ) , ans . end ( ) ) ; for ( auto i : ans ) { return i ; } } } int main ( ) { vector < int > arr = { 5 , 2 , 3 } ; int n = 12 ; cout << findSmallestNumber ( arr , n ) ; return 0 ; }