What would be the most optimum approach to solve this problem.
in the starting of your code store all binarian
b[0]=1;
for(i=1;i<=10000;i++)
b[i]=b[i-1]*2;
ans=0;
now simply answer
for(i=0;i<=n-1;i++)
ans=ans+b[a[i]];
printf("%d\n",ans);
enjoy;
if u are asked to answer modulo M then
b[i]=(b[i-1]%M*2)%M; i think M > 2
and
ans=ans%M+b[a[i]]
Sorry there is slight modification, you need to calculate the length of smallest sub array that has same binarian as A.
one more doubt:
and since a[i] could be up to 10000 so how it can be store in array, 2^10000 is very large no.
for 1st query find sum of all a[i] and compare it with it’s subarrays if condition is true then store number or elements in subarrays and at last print minimum of all.
.
i think u can see that u need to calculate 2^10000 is a big number u can’t store it but ans will be bigger than this as u need to add n terms and all of them can be 10000 so u need to calculate 2^10000+2^10000+2^10000+…
n*(2^10000) so u have to print your ans modulo M.can u store it in a varible (lld)
so my condition in earlier answer that if u need to calculate ans modulo M
b[i]=(b[i-1]%M*2)%M; works here. u won’t get bigger than M;
i worked for you if u appreciated.say me thanks…
Hey, The solution is pretty much straight Forward. We do not need to store or calculate values like 2^a[i].
Lets see how:
First, What is 2^3 (2^x) , 1000. i.e 1 at the xth place. So, to store 2^a[i], we add 1 at a[i]th place in some array, say temp .
Finally, we can have the binary representation of the sum of all 2^a[i] through our array temp .
And we can easily calculate the no. of ones in it, which is our answer.
Link to my Solution in C++ :->
You can easily figure it out, take an example or still, let me know.
Lets take an example,
let n be the number of Input integers, be say n = 6.
And the array be A={1 0 2 0 0 2};
Now create a empty array temp of size 1e6.
Iterate thru A and add 1 to each temp[A[i]] for i 1 to n.
Now the temp array be like,
3 1 2 0 0 0 0 … all 0’s next.
Let sum= 2^A[1] + 2^A[1] + 2^A[2]+ … + 2^A[n].
Which is same as temp[0]* 2^0 + temp[1]* 2^1 + temp[2]* 2^2 + temp[3]* 2^3 … ans so on.
length of the shortest array that has same binarian as that of given array A is the number of 1’s in sum.
overflow will still occur, how it will be handled. And what if element in Array appears more than once.
And once we have computed the sum, I want to calculate the length os shortest subarray whose binarian is same as binarian of Array A.
And what no. of ones would specify, please elaborate more, it would be great help.
@saksham458
You are getting it wrong. There is no overflow, Check my code again.
And I am not computing the exact sum, i am calculating it Binary equivalent and storing it in an array of size 1e6. And we do not need to find any subarray. Please go thru the solution again. I added an example btw.
fr(i,0,1000000)
{
temp[i+1]+= temp[i]/2;
temp[i]%=2;
}
Please explain this part.
The value of a[i] can be max 10,000, then why do we need to create of array size 10^6.
N can be 10^5. In the worst case all A[i] can be 10^4. In that case we will have a vale of 10^5 at index 10^4 in temp Array. So, what i mean is that the binary Representation of sum can exceed the index 10^4 but it cannot exceed 10^6. So to be on the safe side ,i am iterating till 10^6. Do some maths to calculate exactly till where we need to iterate, Quite easy though, @saksham458 . I hope everything is clear now.
fr(i,0,1000000)
{
temp[i+1]+= temp[i]/2;
temp[i]%=2;
}
please explain this logic and how no. of 1’s will be the answer, everything else is sorted now.
Forget about my code. Ask yourself How will you add N numbers Given their Binary representations.
Lets say u have N arrays each containing binary of each A[i]. Now u need to add them all to get the sum.
And to why no. of 1’s is the answer is very obvious, Come up with a counter example, and u will know why… 