Given an array A of N digits, and numbers M1, M2.
Let Conc(A) be the number formed by concatenating the digits in array A. Let Len(A) be the number of digits in A.
Example: for A = [1,3,2], Conc(A) = 132 and Len(A) = 3
Your task is to divide array A into two disjoint non-empty subsequences (X, Y) such that following conditions hold true
Conc(X) is a multiple of M1
Conc(Y) is a multiple of M2
Of all possible divisions, find the minimum value of abs( Len(X) — Len(Y) ), if there is no such possible division then print "-1".
Constraints: 1 <= N, M1, M2 <= 40 1 <= A[i] <= 9
Sliding window. Left window first , right second. From 1 to n. Choose best.
bs, if you dont know dont spread misinformation.
I believe you can apply a dynamic programming approach to this problem. Let $$$dp[i][l][r_1][r_2]$$$ be $$$true$$$ if and only if there exists a division of $$$A[:i]$$$ into two disjoint subsequences $$$(X,Y)$$$ (maybe empty) such that
The base for this dynamic programming would be that for an empty prefix of $$$A$$$ the only $$$true$$$ value corresponds to $$$l=0$$$, $$$r_1=0$$$ and $$$r_2=0$$$. To compute values for $$$A[:i+1]$$$ you can take consider all $$$dp[i][l][r_1][r_2]$$$ and then there will be two cases: $$$A[i+1]$$$ belongs to $$$X$$$ or to $$$Y$$$. So $$$dp[i+1][l+1][(r_1\cdot 10+A[i+1])\ mod\ M_1][r_2]$$$ and $$$dp[i+1][l][r_1][(r_2\cdot 10+A[i+1])\ mod\ M_2]$$$ are $$$true$$$ if $$$dp[i][l][r_1][r_2]$$$ is $$$true$$$.
To obtain the answer it is enough to find all $$$l$$$, such that $$$dp[Len(A)][l][0][0]$$$ is $$$true$$$, and choose the one closest to the $$$\frac{Len(A)}{2}$$$.
The solution will work in $$$O(N^2 \cdot M_1 \cdot M_2)$$$, which should be good enough for given constraints.
Great Solution! Thank you.