10 weeks ago

Rohit • 610

Hyderabad

Question 1

Jerome is an IT professional engineer. He has an old model configured chip in his house, which is not supported in his new laptop. He wants to re-configure it so that it can be used.To re-configure it, he has done many experiments. At last, finally he got a solution. The solution is, in the old chip there are two codes(numbers) written on it X and Y. He has to replace X with a new reconfigured code M.M must be the least number that must include X as the leading digits and it is a multiple of Y

Can you help Jerome with a program that accepts X and Y and prints new reconfigured code M of the chip.

Read the input from STDIN and print the output to STDOUT. Do not write arbitrary strings anywhere in the program, as these contribute to the standard output and test cases will fail.

Constraints:

• X, Y >= 1

Input Format:

The input contains two codes X and Y of the old chip separated by a single white space.

Output Format:

The output must consist of new reconfigured code M of the chip.

Sample Input 1:

33 11

Sample Output 1:

33

Explanation 1:

Old chip two codes, X and Y: 33 and 11.

Here, by the following method of re-configuration,possibilities can be M: 33, 330, 331, 332, and so on.

Here, considering M = 33, its leading digit(s) is X (33) and it is a multiple ofY(11).

Hence, 33 is the new reconfigured code of the chip.

Sample Input 2:

50 3

Sample Output 2:

501

Explanation 2:

Old chip two codes, X and Y: 50 and 3Here, by the following method of re-configuration,possibilities can be M: 50, 500, 501, 502, and so on.

Here, considering M = 501,its leading digit(s)are X(50) and is also multiple of Y(3).

Hence, 501 is the new reconfigured code of the chip.

Question 2

Bob is a studious boy. He is very interested in solving difficult mathematical problems in no time. By seeing his talent, Bob's teacher gave him a problem and asked him to solve it as soon as possible.

The problem was, Bob has been given an arithmetic expression A, the integer P, and M and he has to find the smallest non-negative value of x in expression A such that the remainder of dividing A by M equals P. Consider that solution do exist for the problems provided to him.

Therefore, if the principles of distribution are applied to expression A (Formally, the expression A is a polynomial of the first degree in variable x).

Can you help Bob with a program to solve the problem in a minimum amount of time.

Input Format:

The first line of input contains the expression A.

The second line of input contains two integers P i M.

The arithmetic expression A will only consist of characters , -, , (, ), x, and digits from 0 to 9. The brackets will always be paired, the operators , - and will always be applied to exactly two values (there will not be an expression (-5) or (4 -5)) and all multiplications will be explicit (there will not be an expression 4(5) or 2(x)).

Output Format:

The first and only line of output must contain the smallest non-negative value of variable x.

Constraints:

• A(1 <= |A| <= 105)
• P(0 <= P <= M-1) i M(1 <= M <= 106)

Sample Input 1:

4+x+2

8 9

Sample Output 1:

2

Explanation 1:

Arithmetic expression, A: 4+x+2

P: 8 M: 9

Here, by solving the given equation, we will get:

If x= 0, then the remainder of dividing 4x2 with 9 is 6, which is not equal to P.

If x= 1, then the remainder of division4x2 with 9 is 7,which is not equal to P.

If x= 2, then the remainder of division4x2 with 9 is 8,which is equal to P.

Hence, as an output, it will print 2 as the smallest value of variable x.

Sample Input 2:

2(x+(x+3)9)

2 6

Sample Output 2:

1

Explanation 2:

Arithmetic expression, A: 2(x+(x+3)9)

P: 2 M: 6

Here, by solving the given equation, we will get:

If x= 0, then the remainder of dividing 2 (x+(x+3 ) 9 ) with 6 is 0, which is not equal to P.

If x= 1, then the remainder of division 2 (x+(x+3) 9 ) with 6 is 2,which is equal to P.

Hence, as an output, it will print 1 as the smallest value of variable x.

8 months ago

Shikhar Mehrotra 480

Chennai

Q1) Assuming Y is atmost 10^9

Solution for 1

• Observe that M would be of form M = X * 10^d +Q and 0 < =Q < 10^d, where d is a non-negative integer .

• We want M to be multiple of Y , which implies that M%Y==0

• Therefore , we want to find a pair of values of (d,Q) such that M%Y==0 and M is smallest.

• So for a fixed d, Q%Y should be equal to ( Y - (X * 10^d)%Y ) % Y, for M%Y==0 and since we want Q to be smallest and also Q < 10^d, so if ( Y - (X * 10^d)%Y ) % Y is less than 10^d, then pair (d,( Y - (X * 10^d)%Y ) % Y) is valid choice for our (d,Q).
• Since we want to find the smallest M then the first d for which we get a valid Q as described above then that would be the valid answer and is smallest, ,because for a fixed d we had chosen smallest Q.
• You will always get a valid answer because Y is assumed to be atmost 10^9 , and if d exceeds 8 and modulo Y is already less than 10^9 which means Q will be less than 10^d

Pseudo Code

iterate over d in [0,1,2,3,4,5....10]
{
 Q = (Y - (X*10^d))%Y // to avoid exceeding integer range issues write , Q as (Y - ((X%Y)*((10^d) %Y)))%Y
 if Q is less than 10^d
  {
   we got the answer!! 
   simply print    X*10^d+Q and since it could be large you could print like this [X][000....(d-count of digits(Q))][Q] // print [Q] if Q>0
   break;
  }
}

IMP : If X is given an arbitrarily large string like length is of order 10^5, then you just have to find (X%Y separately)

2.1 years ago

Hardik Gupta • 0

Solution for 2

Parse the given expression string and simplify it . { See below Pseudo - Code }

Clearly Expression A in the question will be of the form A : ax + c1 Lets say for some x1 , after dividing by m , the remainder comes out to be p and quotient q.
Then we need to solve for ax + c1 = mq + p

rearranging , ax - mq = (p-c1)

It is of the form ax + by = c

Now , lets consider the example . Where we have to find the minimum non-integral value of x , which will satisfy the below equation .

ax + by = c.

Clearly , for this to have solution , gcd(a , b) | c as gcd(a , b) will divide the LHS. If given that case , then one solution for it will be

x1 = ca^-1 mod b

y1 = cb^-1 mod a

Now , let g = gcd(a , b)

If we rewrite the above equation as follows :

a(x - kb/g) + b(y - ka/g) = c where k is any integral number { we have just add and subtracted a*b / g term }

Then it is obvious that it will also have the same solutions.

Thus we can represent any solution of this equation as

x = x1 - (k*b)/g

y = y1 + (k*a)/g

It is then easy to find smallest non negative integral values of x by varying k.

Pseudo Code for evaluating Linear expression

def evaluate_expression(expression):

``` This function evaluates all the * and brackets and the final_expression returned contains only + and - sign on numbers and variables.```

returned_expression = ""

if expression[i] == '(':
    store the expression between the brackets in a string and pass it again to the evaluate_expression 
    returned_expression += evalute_expression(expression_between_brackets)
else:
    returned_expression += expression[i]

return returned_expression

def coefficients(expression): This function returns the coefficient of x and constant term in the expression

x_coefficient = 0
constant_term = 0

for i in range(len(expression)):
    if expression[i] == 'x':
        if i == 0:
            x_coefficient += 1
        elif expression[i-1] == '+':
            x_coefficient += 1
        elif expression[i-1] == '-':
            x_coefficient -= 1
        else:
            x_coefficient += int(expression[i-1])
    elif expression[i].isdigit():
        if i == 0:
            constant_term += int(expression[i])
        elif expression[i-1] == '+':
            constant_term += int(expression[i])
        elif expression[i-1] == '-':
            constant_term -= int(expression[i])