Loading Similar Posts

Entering edit mode

Click here to Practice

Submit Problem to OJ

Click here to Practice

Submit Problem to OJ

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
```

Loading Similar Posts