ProveMeRight's blog

Can someone verify? that this question can be solved or it's impossble.
By ProveMeRight, history, 3 years 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?
»
3 years ago, hide # |
← Rev. 4  
Vote: I like it 0 Vote: I do not like it
Hint1
Hint2
Hint3
→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
  • »
    »
    3 years ago, hide # ^ |
     
    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