Entering edit mode

Click here to Practice

Submit Problem to OJ

An e-commerce company is planning to provide cashback points to its customers which can be used for their next purchase .To calculate the cashback point they want to have an algorithm The algorithm will take the order ID P and the amount Q paid for the order as input. It will calculate the cashback points as the minimum number of operations that should be performed to convert the value of the order I to the amount paid for the order The operations that can be performed on order ID are addition (P+P), subtraction (P-F), multiplication (P*P), and division(P/P) in any sequence and at all time. It's not compulsory to app every operation to the order ID.in each cycle only one operation can be applied. After each cycle the value of the order ID is updated with the output of the last operation performed. If this conversion is not possible, the algorithm will return it as -1 anc no cashback points will be provided to the customer. Write an algorithm to calculate the cashback points for the customer . If not possible then print -1

Click here to Practice

Submit Problem to OJ

Question

Jackin, a math teacher at MathWorld is preparing to administer a test to

her class. The students will evaluate an equation that consists of "+ "."-"

and "*" operators. She will award a grade of 'S' for a correct answer and

a grade of 2 for a partially-correct answer featuring a mistake in the

application of the BODMAS rule. If a student's answer is wholly incorrect the student will receive a grade of C

Write an algorithm to help jacklin

find the total class score for the give

question, assuming every student

has answered the question,

Input

The first line of the input consists of

a string S representing the equation

to be evaluated.

The second line consists of an

integer N, representing the total

number of students.

The last line consists of N space-

separated integers - arr1, arr2...arrN representing the answers

given by the students.

Output

Print an integer representing the

total class score for the given

equation.

Constraints

0 ≤ N ≤ 1000

1 ≤ len ≤ 30; where len is the length of S

Entering edit mode

**Question 1:**

`Overview:`

- Given order ID
`P`

and amount`Q.`

- Four possible operations can be done to P
`P = P+P = 2P`

`P = P-P = 0`

`P = P*P = P^2`

`P = P/P = 1`

- Find the minimum number of operations on P to make it equal to Q.

`Approach:`

- Trivial cases:
`P = Q`

minimum number of operations needed = 0`Q = 0`

, minimum number of operations needed = 1, just 1 subtraction is enough.`Q = 1`

, minimum number of operations needed = 1, just 1 division is enough.

- If
`n`

continuous addition is done, then`P`

would become`(2^n)*P.`

- every addition is multiplying P by 2

- If
`n`

continuous multiplication is done, then`P`

would become`P^{2^n}.`

- every multiplication is squaring.

- So, using addition and multiplication, we can get P to be the form
`(2^x)*(P^{2^n}).`

- The power of
`P`

can be changed only by multiplication, so only powers of`P`

possible are of the form`{2^n}`

,`n>=0.`

`P^0`

is also possible, as we can get P to 1 by doing division as the first step.

- The powers of
`2`

obtained can be from both multiplication and addition.- addition increases the existing power of
`2`

by a value of`1.`

- multiplication doubles the existing power of
`2`

. - any power of 2 greater than or equal to zero can be possible.

- addition increases the existing power of

- The power of
- So if the number
`Q`

is the form`(2^x)*(P^{2^n})`

, where`x>=0`

,`n>=0`

.`x = 0`

&`y=0`

minimum number of operations is 1, as`Q = 1`

.- To get
`(P^{2^n})`

, we need exactly`n`

operations (of multiplication).

- To get
`2^x.`

- It is possible to make some additions in between/before the multiplications.
- minimum number of ways with no limit on addition and multiplication is ( no bits in binary representation x + no of ones in the binary representation of x -1)
- (no of bits in binary representation - 1) corresponds to the number of multiplication needed.
`-1`

comes because the leading`1`

in binary representation is not got by multiplication.

- no of
`1`

's correspond to the number of additions needed.

- (no of bits in binary representation - 1) corresponds to the number of multiplication needed.
- Example
`2^10`

is got by:- step 1:
`(2^0 + 2^0 )`

=`2^1`

,`2^{1}`

- step 2:
`(2^1 * 2^1 )`

=`2^2`

,`2^{10}`

- step 3:
`(2^2 * 2^2 )`

=`2^4`

,`2^{100}`

- step 4:
`(2^4 + 2^4 )`

=`2^5`

,`2^{101}`

- step 5:
`(2^5 + 2^5 )`

=`2^10`

,`2^{1010}`

- step 1:
- But here, the number of multiplication is limited by n.
- So, two cases arise:
`n >=`

(no of bits in binary`x`

-1)- then just need to add the additional number of additions needed for
`2^x`

, the final answer is n + (no of ones in the binary representation of x)

- then just need to add the additional number of additions needed for
- else, we need to reduce the number of multiplication to n , and increase the number of additions to compensate for rest of 2^x.
- So just take the last n muliplications done.
- Which will be last x bits in binary representation of x, do the remaining by getting the addition
- example
`x`

is`23`

,`n`

is`2,`

`x`

in binary is`10111`

, so we get last 2 bits as`11`

by muliplication+addition(so`2+2 = 4`

operations),- and remaining
`101`

by addition which is (decimal representation of`101`

) equal to`5`

- so total number of operations needed is
`9`

.

`Cases and solutions:`

`P=Q`

,`ans = 0`

`Q = 0`

,`ans = 1`

.`Q = 1`

,`ans = 1`

.`Q of the form`

P^{2^n}`,`

ans = n``Q of the form 2^n, and P is not a power of 2 or`

P>Q`.`

ans =`no of bits in binary representation of`

n +`no of ones in binary representation of`

n`.`P>Q`

and`Q`

is not the power of two,`ans = -1.`

- If
`Q`

is not of the form`(2^x)*(P^{2^n})`

,`ans = -1`

- In all other case
`Q = (2^x) * (P^{2^n}}`

`n >=`

((no of bits in binary`x`

)-1), then`ans = n +`

no of ones in binary representation of`n`

- Else : let the number of bits in the binary representation of
`x`

be`y`

`ans = n +`

decimal(leading`y-n`

bits in binary representation of`x`

)`+`

no of ones in last`n`

bits in binray representation of`x`

`PseudoCode:`

```
bool checkPowerOfTwo(ll n)
{
if (n == 1)
return true;
else if (n % 2 == 1)
return false;
else
return checkPowerOfTwo(n / 2);
}
vector<int> findBinary(ll n)
{
vector<int> ans;
while (n > 0)
{
ans.push_back(n % 2);
n /= 2;
}
return ans;
}
int cashback(int P, int Q)
{
if(P == Q)
return 0;
else if (Q == 0)
return 1;
else if (Q == 1)
return 1;
else if (checkPowerOfTwo(Q) && (!checkPowerOfTwo(P) || P > Q))
{
vector<int> bin = findBinary(Q);
return bin.size() + __builtin_popcount(Q);
}
else if (P > Q)
return -1;
else
{
int ans = 0;
while (Q % (P * P) == 0)
{
P = P * P;
ans++;
if (P > __INT_MAX__ / P)
break;
}
if (Q % P == 0)
return -1;
else
{
ll Q1 = Q / P;
if (checkPowerOfTwo(Q1))
{
vector<int> bin = findBinary(Q1);
if (ans > bin.size() - 1)
return ans + ____builtin_popcount(Q1);
else
{
ll n = ans;
for (int i = 0; i < n; i++)
{
if (bin[i] == 1)
{
ans++;
}
}
ll x = 1, y = 0;
for (int i = n; i < bin.size(); i++)
{
if (bin[i] == 1)
y += x;
x *= 2;
}
return ans + y;
}
}
else
return -1;
}
}
}
```

Entering edit mode

This problem can be solved using recursion. Iterate on the given expression, and for each operator, divide the expression into two parts. Recursively calculate the possible answers for the left and right part, and then combine the answers for both the parts to get all possible answers for current expression.

```
calculate( val1, val2, operator)
If operator == ‘+’
return val1+val2
else if operator == ‘-’
return val1-val2
else
return val1*val2
correctAnswer(expression)
operators = []
values = []
for char in expression
if char is digit:
// There can be multiple digits in the value
iterate forward to make complete value
values.append(value)
else
while precedence of operators.back >= precedence of char
pop 2 values from the values stack
pop operator from operators stack
values.append(calculate(val1, val2, operator))
operators.append(char)
while operators stack is not empty:
pop 2 values from the values stack
pop operator from operators stack
values.append(calculate(val1, val2, operator))
return values.back
allAnswers(expression, low, high):
if there is no operator anywhere between low and high
return expression.value
possibleAnswers = []
for i from low to high:
if expression[i] is operator
leftAnswers = allAnswers(expression, low, i-1)
rightAnswers = allAnswer(expression, i+1, high)
for val1 in leftAnswers:
for val2 in rightAnswers:
possibleAnswers.append(calculate(val1, val2, expression[i]))
return possibleAnswers
```