24 months ago

Abhimanyu Chadha • 50

Mumbai

Q1

E - Commerce Cashback

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

Q2

BODMAS Rule

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

5 months ago

Lokesh 310

Hyderabad

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;
        }
    }
}

2.9 years ago

Gurankit Pal Singh 160

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