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.