Longest Subsequence from a numeric String divisible by K | C ++ program for the above approach ; Function to if the integer representation of the current string is divisible by K ; Stores the integer representation of the string ; Check if the num is divisible by K ; Function to find the longest subsequence which is divisible by K ; If the number is divisible by K ; If current number is the maximum obtained so far ; Include the digit at current index ; Exclude the digit at current index ; Driver Code ; Printing the largest number which is divisible by K ; If no number is found to be divisible by K
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isdivisible ( string & newstr , long long K ) { long long num = 0 ; for ( int i = 0 ; i < newstr . size ( ) ; i ++ ) { num = num * 10 + newstr [ i ] - '0' ; } if ( num % K == 0 ) return true ; else return false ; } void findLargestNo ( string & str , string & newstr , string & ans , int index , long long K ) { if ( index == ( int ) str . length ( ) ) { if ( isdivisible ( newstr , K ) ) { if ( ( ans < newstr && ans . length ( ) == newstr . length ( ) ) || newstr . length ( ) > ans . length ( ) ) { ans = newstr ; } } return ; } string x = newstr + str [ index ] ; findLargestNo ( str , x , ans , index + 1 , K ) ; findLargestNo ( str , newstr , ans , index + 1 , K ) ; } int main ( ) { string str = "121400" ; string ans = " " , newstr = " " ; long long K = 8 ; findLargestNo ( str , newstr , ans , 0 , K ) ; if ( ans != " " ) cout << ans << endl ; else cout << -1 << endl ; }