Given a number (as string) and two integers a and b, divide the string in two non-empty parts such that the first part is divisible by a and the second part is divisible by b. In case multiple answers exist, return the string such that the first non-empty part has minimum length.
 
Example 1:
Input:
1200 4 3
Output:
12 00
Explanation:
12 is divisible by 4, and
00 is divisible by 3.
 
Example 2:
Input: 
125 12 5
Output: 
12 5
Explanation: 
12 is divisible by 12, and 
5 is divisible by 5.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function stringPartition() which takes the string S and returns a string which will be in the form of first sub-string + " " (Single Space) + second sub-string. If not found return -1 as a string.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1<=N<=10^{6}
1<=a,b<=N

Difficulty: EASY
Tags: Number theory

Data structures

Mathematics

String algorithms
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3

class Solution:

    def stringPartition(ob,S,a,b):

        # Code here



Solutions:
class Solution:

	def stringPartition(ob, S, a, b):
		for i in range(len(S)):
			j = S[:i + 1]
			k = S[i + 1:]
			if len(j) >= 1 and len(k) >= 1:
				if int(j) % a == 0 and int(k) % b == 0:
					return j + ' ' + k
		return -1


class Solution:

	def stringPartition(ob, S, a, b):
		i = 1
		while i < len(S):
			if int(S[:i]) % a == 0 and int(S[i:]) % b == 0:
				return S[:i] + ' ' + S[i:]
			i += 1
		return '-1'


class Solution:

	def stringPartition(ob, S, a, b):
		for i in range(1, len(S)):
			s1 = S[:i]
			s2 = S[i:]
			x = int(s1)
			y = int(s2)
			if x % a == 0 and y % b == 0:
				s = s1 + ' ' + s2
				return s
		return '-1'


class Solution:

	def stringPartition(ob, S, a, b):
		c = 0
		ans = ''
		for i in range(1, len(S)):
			if int(S[0:i]) % a == 0 and int(S[i:]) % b == 0:
				ans += S[0:i] + ' ' + S[i:]
				return ans
		return -1


class Solution:

	def stringPartition(ob, S, a, b):
		for i in range(1, len(S)):
			if not int(S[:i]) % a:
				if not int(S[i:]) % b:
					return S[:i] + ' ' + S[i:]
		return -1


class Solution:

	def stringPartition(ob, S, a, b):
		for i in range(1, len(S)):
			str_1 = S[:i]
			str_2 = S[i:]
			int_check_1 = int(str_1)
			int_check_2 = int(str_2)
			if int_check_1 % a == 0 and int_check_2 % b == 0:
				crt_ans = str_1 + ' ' + str_2
				return crt_ans
		return '-1'


class Solution:

	def stringPartition(ob, S, a, b):
		n = len(S)
		for i in range(1, n):
			(s1, s2) = (S[:i], S[i:])
			if int(s1) % a == 0 and int(s2) % b == 0:
				return s1 + ' ' + s2
		return -1


class Solution:

	def stringPartition(ob, S, a, b):
		for i in range(1, len(S)):
			subs = S[i:]
			subl = S[:i]
			x = int(subs)
			y = int(subl)
			if x % b == 0 and y % a == 0:
				return subl + ' ' + subs
		return '-1'


class Solution:

	def stringPartition(ob, S, a, b):
		length = len(S)
		i = 1
		while i < length:
			(part1, part2) = (S[:i], S[i:])
			if int(part1) % a or int(part2) % b:
				i += 1
			else:
				return part1 + ' ' + part2
		return -1


class Solution:

	def stringPartition(ob, S, a, b):
		lenn = len(S)
		lr = [0] * (lenn + 1)
		lr[0] = int(S[0]) % a
		for i in range(1, lenn):
			lr[i] = (lr[i - 1] * 10 % a + int(S[i])) % a
		rl = [0] * (lenn + 1)
		rl[lenn - 1] = int(S[lenn - 1]) % b
		power10 = 10
		for i in range(lenn - 2, -1, -1):
			rl[i] = (rl[i + 1] + int(S[i]) * power10) % b
			power10 = power10 * 10 % b
		ans = ''
		for i in range(0, lenn - 1):
			if lr[i] != 0:
				continue
			if rl[i + 1] == 0:
				for k in range(0, i + 1):
					ans += S[k]
				ans += ' '
				for k in range(i + 1, lenn):
					ans += S[k]
				return ans
		return '-1'


class Solution:

	def stringPartition(ob, S, a, b):
		s = 0
		n = len(S)
		for i in range(1, n):
			curr_num1 = S[:i]
			curr_num2 = S[i:]
			if int(curr_num1) % a == 0 and int(curr_num2) % b == 0:
				ans = '{} {}'.format(curr_num1, curr_num2)
				return ans
		return '-1'


class Solution:

	def stringPartition(ob, S, a, b):
		for i in range(1, len(S)):
			first = int(S[:i])
			second = int(S[i:])
			if first % a == 0 and second % b == 0:
				return S[:i] + ' ' + S[i:]
		return '-1'


class Solution:

	def stringPartition(ob, S, a, b):
		k = 1
		while k < len(S):
			x = S[:k]
			y = S[k:]
			i = int(x)
			j = int(y)
			if i % a == 0 and j % b == 0:
				ans = x + ' ' + y
				return ans
			k += 1
		return '-1'


class Solution:

	def stringPartition(ob, S, a, b):
		for i in range(1, len(S)):
			l1 = S[:i]
			l2 = S[i:]
			int1 = int(l1)
			int2 = int(l2)
			if int1 % a == 0 and int2 % b == 0:
				sum = l1 + ' ' + l2
				return sum
		return -1


class Solution:

	def stringPartition(ob, s, a, b):
		s1 = ''
		s2 = ''
		if a == 1:
			if len(s) > 1:
				for i in range(1, len(s)):
					if int(s[i:len(s)]) % b == 0:
						s1 = s[0:i]
						s2 = s[i:len(s)]
						break
		else:
			for i in range(0, len(s)):
				if int(s[0:i + 1]) % a == 0:
					s1 = s[0:i + 1]
					for j in range(i + 1, len(s)):
						if int(s[j:len(s)]) % b == 0:
							s2 = s[i + 1:len(s)]
							break
					break
		if len(s1) > 0 and len(s2) > 0:
			return s1 + ' ' + s2
		else:
			return '-1'


class Solution:

	def stringPartition(ob, S, a, b):
		ar = str(S)
		n = len(ar)
		for i in range(1, n):
			if int(ar[0:i]) % a == 0 and int(ar[i:n]) % b == 0:
				ans = ar[0:i] + ' ' + ar[i:]
				return ans
		return '-1'
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(S, a, b) = map(str, input().strip().split(' '))
		a = int(a)
		b = int(b)
		ob = Solution()
		print(ob.stringPartition(S, a, b))


class Solution:

	def stringPartition(ob, S, a, b):
		for i in range(1, len(S)):
			x1 = S[:i]
			x2 = S[i:]
			x1_int = int(x1)
			x2_int = int(x2)
			if x1_int % a == 0 and x2_int % b == 0:
				return x1 + ' ' + x2
		return -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(S, a, b) = map(str, input().strip().split(' '))
		a = int(a)
		b = int(b)
		ob = Solution()
		print(ob.stringPartition(S, a, b))


class Solution:

	def stringPartition(ob, S, a, b):
		for i in range(1, len(S)):
			s1 = S[:i]
			s2 = S[i:]
			x = int(s1)
			y = int(s2)
			if x % a == 0 and y % b == 0:
				ans = s1 + ' ' + s2
				return ans
		return '-1'
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(S, a, b) = map(str, input().strip().split(' '))
		a = int(a)
		b = int(b)
		ob = Solution()
		print(ob.stringPartition(S, a, b))


class Solution:

	def stringPartition(ob, S, a, b):
		ans = []
		for i in range(1, len(S)):
			if int(S[:i]) % a == 0 and int(S[i:]) % b == 0:
				ans.append(S[:i])
				ans.append(S[i:])
				break
		if len(ans) == 0:
			return '-1'
		return ' '.join(ans)


class Solution:

	def stringPartition(ob, S, a, b):
		for i in range(1, len(S)):
			st = S[0:i]
			st2 = S[i:]
			val1 = int(st)
			val2 = int(st2)
			if val1 % a == 0 and val2 % b == 0:
				resstr = st + ' ' + st2
				return resstr
		return -1


class Solution:

	def stringPartition(ob, S, a, b):
		for i in range(1, len(S)):
			x = S[:i]
			y = S[i:]
			a1 = int(x)
			a2 = int(y)
			if a1 % a == 0 and a2 % b == 0:
				return x + ' ' + y
		return -1


class Solution:

	def stringPartition(ob, S, a, b):
		for i in range(len(S) - 1):
			first_part = S[0:i + 1]
			second_part = S[i + 1:]
			if int(first_part) % a == 0 and int(second_part) % b == 0:
				return first_part + ' ' + second_part
		return -1


class Solution:

	def stringPartition(ob, S, a, b):
		S = str(S)
		al = []
		bl = []
		for i in range(len(S) - 1):
			if int(S[0:i + 1]) % a == 0 and int(S[i + 1:]) % b == 0:
				al.append(S[0:i + 1])
				bl.append(S[i + 1:])
		if len(al) == 0 and len(bl) == 0:
			return -1
		mn = min(al, key=len)
		ind = al.index(mn)
		mn1 = bl[ind]
		return '{0} {1}'.format(mn, mn1)


class Solution:

	def stringPartition(ob, S, a, b):
		l1 = []
		output = ''
		for i in range(len(S)):
			output += S[i]
			if int(output) % a == 0:
				index1 = i
				output1 = S[index1 + 1:]
				if len(output1) == 0:
					return -1
				if int(output1) % b == 0:
					l1.append(S[:index1 + 1])
					l1.append(S[index1 + 1:])
					return ' '.join(l1)
		if len(l1) == 0:
			return -1


class Solution:

	def stringPartition(ob, s, a, b):
		n = len(s)
		for i in range(1, n):
			fp = s[:i]
			sp = s[i:]
			if int(fp) % a == 0 and int(sp) % b == 0:
				return fp + ' ' + sp
		return -1


class Solution:

	def stringPartition(ob, s, a, b):
		n = len(s)
		fp = ''
		sp = ''
		fp_found = False
		sp_found = False
		for i in range(0, n):
			fp += s[i]
			if int(fp) % a == 0:
				fp_found = True
				for j in range(i + 1, n):
					sp += s[j]
					if int(sp) % b == 0:
						sp_found = True
				if sp_found == True:
					break
				else:
					sp = ''
		if fp_found == False or sp_found == False:
			return -1
		else:
			ans = fp + ' ' + sp
			return ans


class Solution:

	def stringPartition(ob, S, a, b):
		i = 0

		def dfs(i):
			if i == len(S):
				return '-1'
			num1 = S[:i + 1]
			num2 = S[i + 1:]
			if num1 and num2 and (int(num1) % a == 0) and (int(num2) % b == 0):
				return num1 + ' ' + num2
			return dfs(i + 1)
		ans = dfs(0)
		return ans


class Solution:

	def stringPartition(ob, S, a, b):
		for i in range(1, len(S)):
			t = S[:i]
			t1 = S[i:]
			if int(t) % a == 0 and int(t1) % b == 0:
				res = t + ' ' + t1
				return res
		return -1


class Solution:

	def stringPartition(ob, S, a, b):
		for x in range(1, len(S)):
			part1 = S[:x]
			part2 = S[x:]
			if int(part1) % a == 0 and int(part2) % b == 0:
				return part1 + ' ' + part2
		return -1


class Solution:

	def stringPartition(ob, s, a, b):
		for i in range(1, len(s)):
			l1 = int(s[:i]) % a
			l2 = int(s[i:]) % b
			if (l1 == 0) & (l2 == 0):
				return s[:i] + ' ' + s[i:]
		return -1


class Solution:

	def stringPartition(ob, S, a, b):
		str1 = ''
		str2 = ''
		found = False
		for i in range(len(S)):
			str1 += S[i]
			n1 = int(str1)
			if n1 % a == 0:
				str2 = ''
				str2 += S[i + 1:len(S)]
				if str2 != '':
					n2 = int(str2)
				else:
					n2 = 1.01
				if n2 % b == 0:
					found = True
					break
		if found:
			return str1 + ' ' + str2
		return '-1'


class Solution:

	def stringPartition(ob, S, a, b):
		for i in range(len(S) - 1):
			f = S[:i + 1]
			s = S[i + 1:]
			if int(f) % a == 0 and int(s) % b == 0:
				r = f + ' ' + s
				return r
		return -1


class Solution:

	def stringPartition(ob, S, a, b):
		arr = []
		l = len(S)
		for i in range(1, l):
			if int(S[0:i]) % a == 0:
				arr.append(S[0:i])
			else:
				continue
		if arr == []:
			return -1
		else:
			arr.sort()
		count = 0
		for i in arr:
			new = S[len(i):l]
			if int(new) % b == 0:
				ans = i + ' ' + new
				count = 1
				break
			else:
				continue
		if count == 1:
			return ans
		else:
			return -1


class Solution:

	def stringPartition(ob, s, a, b):
		n = len(s)
		l = [0] * n
		r = [0] * n
		l[0] = int(s[0]) % a
		for i in range(1, n):
			l[i] = (l[i - 1] * 10 + int(s[i])) % a
		r[n - 1] = int(s[n - 1]) % b
		pw = 10
		for i in range(n - 2, -1, -1):
			r[i] = (r[i + 1] + int(s[i]) * pw) % b
			pw = pw * 10 % b
		for i in range(n - 1):
			if l[i] == 0 and r[i + 1] == 0:
				return s[0:i + 1] + ' ' + s[i + 1:]
		return -1


class Solution:

	def stringPartition(ob, S, a, b):
		num = 0
		idx = 0
		L = len(S)
		while idx < L:
			num = num * 10 + int(S[idx])
			idx += 1
			if num % a == 0:
				break
		if num % a == 0:
			while idx < L and int(S[idx:]) % b != 0:
				num = num * 10 + int(S[idx])
				idx += 1
			if idx < L and int(S[idx:]) % b == 0 and (num % a == 0):
				return str(num) + ' ' + S[idx:]
		return '-1'


class Solution:

	def stringPartition(ob, S, a, b):
		p = 1
		res = ''
		while p < len(S):
			left = S[0:p]
			right = S[p:]
			leftv = int(left)
			rightv = int(right)
			if leftv % a == 0 and rightv % b == 0:
				res = str(left) + ' ' + str(right)
				break
			p = p + 1
		if res == '':
			return -1
		return res


class Solution:

	def stringPartition(ob, S, a, b):
		l = 1
		ans = ''
		while l < len(S):
			left = S[0:l]
			right = S[l:]
			lefti = int(left)
			righti = int(right)
			if lefti % a == 0 and righti % b == 0:
				ans = str(left) + ' ' + str(right)
				break
			l = l + 1
		if ans == '':
			return -1
		return ans


class Solution:

	def stringPartition(ob, S, a, b):
		l = len(S)
		for i in range(1, l):
			left = int(S[:i])
			right = int(S[i:])
			if left % a == 0 and right % b == 0:
				return S[:i] + ' ' + S[i:]
		return '-1'


class Solution:

	def stringPartition(ob, S, a, b):
		n = len(S)
		for i in range(1, n):
			p = int(S[:i])
			q = int(S[i:])
			if p % a == 0 and q % b == 0:
				out = S[:i] + ' ' + S[i:]
				return out
		return '-1'


class Solution:

	def stringPartition(ob, s, a, b):
		arr = []
		k = ''
		k += s[0]
		for i in range(1, len(s)):
			if int(k) % a == 0 and int(s[len(k):]) % b == 0:
				arr.append(k)
				arr.append(s[len(k):])
				return ' '.join(arr)
			else:
				k += s[i]
		return '-1'


class Solution:

	def stringPartition(ob, S, a, b):
		n = int(S)
		l = ''
		m = len(S)
		c = 0
		p = 0
		for j in range(m - 1):
			i = S[j]
			c += 1
			p = p * 10 + int(i)
			q = n - p * pow(10, m - c)
			if p % a == 0 and q % b == 0:
				return S[:j + 1] + ' ' + S[j + 1:]
		return '-1'


class Solution:

	def stringPartition(ob, S, a, b):
		s = ''
		for i in S:
			s += i
			if s == S:
				return -1
			if int(s) % a == 0 and int(S[len(s):]) % b == 0:
				break
		s += ' '
		s += S[len(s) - 1:]
		return s


class Solution:

	def stringPartition(ob, s, a, b):
		flag = 0
		for i in range(1, len(s)):
			Na = int(s[:i])
			Nb = int(s[i:])
			if Na % a == 0 and Nb % b == 0:
				flag = 1
				return s[:i] + ' ' + s[i:]
		if flag == 0:
			return -1


class Solution:

	def stringPartition(ob, S, a, b):
		for i in range(len(S)):
			s = int(S[:i + 1], base=10)
			if s % a == 0:
				if S[i + 1:] != '' and int(S[i + 1:], base=10) % b == 0:
					return S[:i + 1] + ' ' + S[i + 1:]
		return -1


class Solution:

	def stringPartition(ob, s, z, x):
		for i in range(1, len(s)):
			a = int(s[0:i])
			b = int(s[i:])
			if a % z == 0 and b % x == 0:
				return s[0:i] + ' ' + s[i:]
		return -1


class Solution:

	def stringPartition(ob, S, a, b):
		l = list(S)
		for i in range(1, len(l)):
			p = l[0:i]
			q = l[i:]
			r = ''.join(p)
			s = ''.join(q)
			t = int(r)
			u = int(s)
			if t % a == 0 and u % b == 0:
				return r + ' ' + s
		return '-1'


class Solution:

	def stringPartition(ob, S, a, b):
		o = int(S)
		d = 0
		k = len(S) - 1
		i = 0
		c = 0
		while k:
			d = d * 10 + int(S[i])
			e = o - d * pow(10, k)
			if d % a == 0 and e % b == 0:
				c = 1
				break
			k = k - 1
			i = i + 1
		if c == 1:
			n = len(str(d))
			return S[:n] + ' ' + S[n:]
		return -1


import time

class Solution:

	def stringPartition(ob, s, a, b):
		t = time.time()
		idx = -1
		n = len(s)
		frst = ''
		sec = ''
		for i in range(n):
			frst += s[i]
			idx = i
			if int(frst) % a == 0:
				if idx == n - 1:
					return -1
				else:
					sec = ''
					for j in range(idx + 1, n):
						sec += s[j]
					if int(sec) % b == 0:
						return frst + ' ' + sec
					else:
						continue
		return -1