TOR

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

  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:

NameTypeDescription
nintegerThe length of a and b
cstringThe 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
#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;
}
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);
}
}
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))