May long challenge (reduce to one)program
while i implementing this code in java finally i got last list very big and it get overflow of datatype which i declare it(such as int,long,Biginteger). so i getting wrong answer while submitting
can anyone give any alternative to this problem plzzz
The problem is quite simple if you work out some maths behind this.
Actually the order won’t matter and so basically you start from 1 & 2 and apply the given formula (work it out on a paper and simplify it) so you would get the final formula as
ANS = (n+1)! - 1
The correct order of the answer will be when you start from the lower numbers first. (Because of the multiplication term, At any point, you want to maximize the final answer hence multiplying with a smaller number later will give a lower answer.)
So after that, since the queries are 10^5 you can preprocess the answer beforehand for all n and then answer in O(1) using DP.
DP[1] = 1
DP[i] = (DP[i-1] + i + i * dp[i-1] )% mod
Hope it helps.
The order of the operations don’t matter since all the elements are unique and permutation of first N natural numbers. So let’s say you have an array of n integers:
[A0, A1, A2…An-1]
Let’s say I select the first two numbers from the list and apply the formula
A0 + A1 + A0A1 = X (let)
I could then remove these two elements and store this result as the first element (since the order doesn’t matter).
Now my list reduces to:
[X, A2…An-1]
Now if I’m to apply it to the first two elements again, you can see that I’m using the previously computed result in the current calculation,
which smells like DP. You don’t in fact need to create a list here since we can treat a[i] as i as per the given problem.
So to calculate the result at the ith position (dp[i]), I use X = dp[i-1], Y = i and obtain the recurrence, which you can then preprocess it in O(n) and answer each test case in O(1).
As for the base condition, our recurrence depends on one previous term so we’ll need one base condition. The problem asks us to select two integers, but what if we have only one integer to begin with? That should be 1 as per the problem and the end of the operations. The recurrence has already been mentioned by rgkbitw, but I’ll write it once again. Take care of the overflow.
dp1 = 1 (assuming 1 based indexing)
dpi = (dpi-1 + i + i*dpi-1) % MOD
Final Complexity: O(n+t)
it is quite simple.
Start with 1,2…then go upto n applying the same formula a + b + ab.
Now add 1 and subtract one and make factors using that and keep -1 aside.
so you will get (n+1)! - 1 each time you do this thing!
Or take any two you get x + y +xy = (1+x)(1+y) - 1
take this with z and get (((1+x)(1+y) - 1) + 1)(1+z) - 1
So combining anythree numbers will give formula (1+x)(1+y)(1+z) - 1
By induction we can prove for combining list of any n numbers in ANY order its (1+x1)(1+x2)(1+x3)……(1+xn) - 1
Please comment if I am wrong
Can you please provide the code for more clarity about preprocessing it and answering it in o(1).
How does one prove that the order of the calculation doesn’t matter here?