TOR

November 23, 2021

TOR

Here, in this page we will discuss one of the problem TOR that was asked in InfyTQ Advance Coding Section. We will discuss the problem description along with function description, Test Cases along with there explanation.

You will find the solution of the problem in different programming language.

TOR 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)).

Go through the digits one by one .
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:

Name	Type	Description
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

C++

Java

Python

C++

#include <bits/stdc++.h>
using namespace std;
string s;
int n;
bool ch;
int fun(int i,int num)
{
    if(i==s.length()) return num;//cout<<num<<endl;
    if(ch)  return fun(i+1,num*10);
 
    if(s[i]=='0') return fun(i+1,num*10);
    if(s[i]=='2') return fun(i+1,num*10 + 1);
    
    if(i==0) return fun(i+1,2);
    ch=true;
    return fun(i+1,num*10+1);
 
}
 
int main()
{
    cin>>n;
    ch=false;
    cin>>s;
    cout << fun(0,0)%1000000007;
}

Java

import java.util.*;
class Main {
    static String s;
    static int n;
    static Boolean ch;
    static int fun(int i, int num) {
        if (i == s.length())
            return num;

        if (ch)
            return fun(i + 1, num * 10);

        if (s.charAt(i) == '0')
            return fun(i + 1, num * 10);

        if (s.charAt(i) == '2')
            return fun(i + 1, num * 10 + 1);

        if (i == 0)
            return fun(i + 1, 2);

        ch = true;
        return fun(i + 1, num * 10 + 1);
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        s = sc.next();
        ch = false;
        System.out.println(fun(0, 0) % 1000000007);
    }
}

Python

ch=False
n=int(input())
s=input()
def fun(i,num,ch):
    if i==n:
        return num 
    if ch:
        return fun(i+1,num*10,ch)
    if s[i]=='0':
        return fun(i+1,num*10,ch)
    if s[i]=='2':
        return fun(i+1,num*10+1,ch)
    if i==0:
        return fun(i+1,2,ch)
    ch=True
    return fun(i+1,num*10+1,ch)
    
print(fun(0,0,ch))