Given a large number , check if a subsequence of digits is divisible by 8 | Function takes in an array of numbers , dynamically goes on the location and makes combination of numbers . ; Converting string to integer array for ease of computations ( Indexing in arr [ ] is considered to be starting from 1 ) ; If we consider the number in our combination , we add it to the previous combination ; If we exclude the number from our combination ; If at dp [ i ] [ 0 ] , we find value 1 / true , it shows that the number exists at the value of ' i ' ; Driver Code
< ? php function isSubSeqDivisible ( $ str ) { $ n = strlen ( $ str ) ; $ dp = array_fill ( 0 , $ n + 1 , array_fill ( 0 , 10 , NULL ) ) ; $ arr = array_fill ( 0 , ( $ n + 1 ) , NULL ) ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) $ arr [ $ i ] = $ str [ $ i - 1 ] - '0' ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) { $ dp [ $ i ] [ $ arr [ $ i ] % 8 ] = 1 ; for ( $ j = 0 ; $ j < 8 ; $ j ++ ) { if ( $ dp [ $ i - 1 ] [ $ j ] > $ dp [ $ i ] [ ( $ j * 10 + $ arr [ $ i ] ) % 8 ] ) $ dp [ $ i ] [ ( $ j * 10 + $ arr [ $ i ] ) % 8 ] = $ dp [ $ i - 1 ] [ $ j ] ; if ( $ dp [ $ i - 1 ] [ $ j ] > $ dp [ $ i ] [ $ j ] ) $ dp [ $ i ] [ $ j ] = $ dp [ $ i - 1 ] [ $ j ] ; } } for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) { if ( $ dp [ $ i ] [ 0 ] == 1 ) return true ; } return false ; } $ str = "3144" ; if ( isSubSeqDivisible ( $ str ) ) echo " Yes " ; else echo " No " ; ? >