I was trying to solve this problem for 2 hours and couldn't build a solution of it. Please try to give this problem a try and let me know in comments sections, if you could solve it. Btw, what would be the difficulty of this problem?

Problem Statement-: Lets define Ternary numbers to be the positive integer numbers that consist of digits 0,1,2 only. Let’s also define the operation TOR(x,y) to be the following operation on two Trenary numbers x and y (its output is z = TOR(x,y)).

1. Go through the digits one by one .
2. For each digit i, the digit i in the output will be z[i] = (x[i] + y[i]) % 3

You are given a positive integer n, and a long positive integer c, your job is to find two Ternary numbers a,b (of length n) where c = TOR(a,b) and max(a,b) is as minimum as possible. After finding that pair output max(a,b). If there’s no such pair, output -1.

Note 1: the given numbers won’t have any leading zeros.
Note 2: a,b should be of length n without leading zeros.
Note 3: since the answer can be very large, output it modulo 1000000007 (10^9 +7).

Function Description:

Complete the TOR function in the editor below. It has the following parameters(s):

Parameters:

n -> integer -> The length of a and b
c -> string -> The number which should satisfy the equation c=TOR(a,b).

The function must return an INTEGER denoting the max(a,b) when it’s minimized.

Constraints:

1 <= n <= 10^5
1 <= len(c) <= 2*n

Input Format

The first line contains an integer, n, denoting the length of a and b .
The next line contains a string, c, denoting the number which should satisfy the equation c=TOR(a,b).

Sample Cases:

Sample input 1

2
22

Sample output
11