ProveMeRight's blog

Can someone verify? that this question can be solved or it's impossble.
By ProveMeRight, history, 19 months ago, In English

let's suppose the case:

k = 1, n = 1000;

arr[] = {1,3,5,7,9,11,..........1999]

For this case, the answer can be 2^N, and according to the question we have to return an integer. Is it possible?

Please help someone.

Thank you.

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
19 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it
Hint1
Hint2
Hint3
→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    hint4: Read the issues mentioned in the blog first, rather than rushing to growing contribution.

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it
      Hint5
      → Reply
»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Since n<=10^3 we can solve the problem in O(n^2) by the naive implementation of biginteger.

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Yes, it is possible. $$$2^{1000}$$$, which is the largest possible answer, has roughly $$$300$$$ digits. Multiplying numbers to get to a $$$300$$$ digits number shouldn't be too slow. If you still get TLE, you can just represent bigInt using base $$$10^{9}$$$, which would bring the number of digits down to a laughable $$$34$$$. If you are using Python then time limit shouldn't be a problem as well, as Python has built-in Karatsuba multiplication algorithm, which is fast.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Multiplying $$$k$$$ numbers (polynomials) in the case when answer has $$$n$$$ digits is $$$O(n^2)$$$. One may prove it with a reasoning simar to the one behind $$$O(n^2)$$$ knapsack on trees.

    → Reply