Question: Flipkart Recent Asked Coding Round Question in IIT Delhi
1
Entering edit mode
ADD COMMENTlink 22 days ago Abhimanyu Chadha 10 • updated 20 days ago Manas KV • 0
4
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.
  • 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.
    • 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}
    • 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)
      • 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 formP^{2^n},ans = n`
  • Q of the form 2^n, and P is not a power of 2 orP>Q.ans =no of bits in binary representation ofn +no of ones in binary representation ofn`.
  • 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;
        }
    }
}
ADD COMMENTlink 20 days ago Lokesh 230
1
Entering edit mode

Solution for question 2

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.

Pseudo Code:

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
ADD COMMENTlink 21 days ago Gurankit Pal Singh 120

Login before adding your answer.

Similar Posts
Loading Similar Posts