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

My thoughts: I am really clueless over here. The best approach I could come up with is brute force where we iterate over all possible X and thus corresponding Y (time complexity = O(2^N)) I thought that for each iteration, one could calculate the integers Conc(X), Conc(Y) and check for divisibility with M1, M2. But considering that the size of A can be 40, Conc(X) would not fit in any data type even for the case when len(X) is >20.

Any help would be great, please!