Square StringThe sqing value for a binary string 𝑆S of length 𝑁N is calculated as follows:Let 𝑋=0X=0 be the initial sqing value.For each 𝑖i from 11 to 𝑁N, let 𝑗j be the largest index such that 1≤𝑗<𝑖1≤j<i and 𝑆𝑗≠𝑆𝑖S j​ =S i​ .If such an index 𝑗j exists, add (𝑖−𝑗)2(i−j) 2 to 𝑋X, otherwise do nothing.For example, consider 𝑆=000110S=000110.For 𝑖=1,2,3i=1,2,3, there is no 𝑗<𝑖j<i such that 𝑆𝑗≠𝑆𝑖S j​ =S i​ .For 𝑖=4i=4 and 𝑖=5i=5, we find 𝑗=3j=3, and add (4−3)2=1(4−3) 2 =1 and (5−3)2=4(5−3) 2 =4 to the answer, respectively.For 𝑖=6i=6, we find 𝑗=5j=5 and add (6−5)2=1(6−5) 2 =1 to the answer.The sqing value is thus 1+4+1=61+4+1=6.You are given 𝑁N. There are 2𝑁2 N binary strings of length 𝑁N.Find the sum of all their sqing values.This sum can be large, so compute it modulo 109+710 9 +7.As a reminder, a binary string is a string whose characters are all either 00 or 11.Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.The first and only line of each test case contains a single integer 𝑁N — the length of the binary strings to be considered.Output FormatFor each test case, output on a new line the answer, modulo 109+710 9 +7.Constraints1≤𝑇≤10001≤T≤10001≤𝑁≤5⋅1051≤N≤5⋅10 5 The sum of 𝑁N over all test cases won't exceed 5⋅1055⋅10 5 .Sample 1:InputOutput323838216839372959Explanation:Test case 11: The possible strings are {"00","01","10","11"}{"00","01","10","11"}.The sqing value for "00""00" is 00.The sqing value for "01""01" is 11 (for 𝑖=2i=2, we find 𝑗=1j=1).The sqing value for "10""10" is 11 (for 𝑖=2i=2, we find 𝑗=1j=1).The sqing value for "11""11" is 00.Hence, the answer to this test case is 22.Test case 22: There are 88 binary strings of length 33.The sqing value for "000""000" is 00The sqing value for "001""001" is 11The sqing value for "010""010" is 22The sqing value for "011""011" is 55The sqing value for "100""100" is 55The sqing value for "101""101" is 22The sqing value for "110""110" is 11The sqing value for "111""111" is 00Hence, the answer to this test case is 1616.

Propose a binary search algorithm, 𝐵𝐵, that decides the perfect square problem.

The two versions of the problem are different. You may want to read both versions. You can make hacks only if both versions are solved.You are given an array a𝑎 of length n𝑛. Start with c=0𝑐=0. Then, for each i𝑖 from 11 to n𝑛 (in increasing order) do exactly one of the following:Option 11: set c𝑐 to c+ai𝑐+𝑎𝑖.Option 22: set c𝑐 to |c+ai||𝑐+𝑎𝑖|, where |x||𝑥| is the absolute value of x𝑥.Let the maximum final value of c𝑐 after the procedure described above be equal to k𝑘. Find k𝑘.InputThe first line contains a single integer t𝑡 (1≤t≤1041≤𝑡≤104) — the number of test cases.The first line of each test case contains a single integer n𝑛 (2≤n≤2⋅1052≤𝑛≤2⋅105).The second line of each case contains n𝑛 integers a1𝑎1, a2𝑎2, a3𝑎3, ……, an𝑎𝑛 (−109≤ai≤109−109≤𝑎𝑖≤109).The sum of n𝑛 over all test cases does not exceed 3⋅1053⋅105.OutputFor each test case, output a single integer — the value of k𝑘.ExampleinputCopy5410 -9 -3 481 4 3 4 1 4 3 43-1 -2 -34-1000000000 1000000000 1000000000 100000000041 9 8 4outputCopy6246400000000022NoteIn the first test case, if we set c𝑐 to its absolute value every time we add to it, we end up with 66. It can be shown that this is the maximum result.In the second test case, taking the absolute value will never change anything, so we can just sum the array without doing anything to get 2424.In the third test case, it is optimal to wait until the end to set c𝑐 to its absolute value, resulting in an answer of 66.

Mary is working to find the square root of a number in C++ language using a binary search algorithm. Which of the following options can she perform to get an optimized solution?Constraints0<=x<=2^31-1Optionsint fun(int x) { if(x==1) return x; int low=0,high=x; int res=0; while(low<high){ int mid=(low+high)/2; if(mid>x/mid) high=mid; else{ res=mid; low=mid+1; } } return res;}int fun(int x) { if(x==1) return x; int low=0,high=x; int res=0; while(low<=high){ int mid=low+(high-low)/2; if(mid>x/(mid*mid) high=mid; else{ res=mid; low=mid+1; } } return res;}int fun(int x) { if(x==1) return x; int low=0,high=x; int res=0; while(low<high){ int mid=low+(high-low)/2; else if((mid*mid*mid)>x) high=mid; else{ res=mid; low=mid+1; } } return res;}int fun(int x) { int res=0; for(int i=0;i<=x;i++){ if((i*i)<=x) res=i; } return res;}

Make My Array EqualYou are given an array 𝐴A of length 𝑁N.Determine if it is possible to make all the elements of 𝐴A equal by performing the following operation any number of times (possibly, zero):Choose two distinct indices 𝑖i and 𝑗j (1≤𝑖,𝑗≤𝑁1≤i,j≤N, 𝑖≠𝑗i=j); andUpdate the value at index 𝑖i by setting 𝐴𝑖A i​ to 𝐴𝑖+𝐴𝑗A i​ +A j​ .For example, if 𝐴=[1,5,3,5,6]A=[1,5,3,5,6],Choosing 𝑖=5i=5 and 𝑗=3j=3 would result in the array [1,5,3,5,9][1,5,3,5,9], since we replace 𝐴5A 5​ with 𝐴5+𝐴3=9A 5​ +A 3​ =9.Choosing 𝑖=2i=2 and 𝑗=4j=4 would instead result in the array [1,10,3,5,6][1,10,3,5,6].Output "YES" if it is possible to make all elements of the array equal after performing several (possibly, zero) of these operations, otherwise output "NO" (without quotes).Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.Each test case consists of two lines of input.The first line of each test case contains a single integer 𝑁N — the length of array.The second line of each test case contains 𝑁N space-separated integers 𝐴1,𝐴2,…,𝐴𝑁A 1​ ,A 2​ ,…,A N​ , denoting the initial array.Output FormatFor each test case, print Yes if it is possible to make all elements of array equal using any number of operations, otherwise print No.You may print each character of the output in either uppercase or lowercase (for example, the strings YES, yEs, yes, and yeS will all be treated as identical).Constraints1≤𝑇≤1051≤T≤10 5 1≤𝑁≤2⋅1051≤N≤2⋅10 5 0≤𝐴𝑖≤1090≤A i​ ≤10 9 The sum of 𝑁N over all test cases won't exceed 2⋅1052⋅10 5 .Sample 1:InputOutput331 1 121 231 0 0YESNOYES

Given a binary string s. Perform r iterations on string s, where in each iteration 0 becomes 01 and 1 becomes 10. Find the nth character (considering 0 based indexing) of the string after performing these r iterations (see examples for better understanding).