Forwarded from Aman Raj
There is a tree with NN vertices, rooted at vertex 11. Vertex ii has the value A_iA
i
written on it.
Alice walks along this tree, starting at the root.
When she is at vertex uu:
If uu has no children, she stops.
Otherwise, suppose uu has cc children. She picks one of them at random (each one has a \frac{1}{c}
c
1
probability of being picked), and then moves to it.
Alice also has a score, defined as follows:
Let the vertices she visited be u_1, u_2, \ldots, u_ku
1
,u
2
,…,u
k
Then, she will forget exactly one of these kk vertices; and her score will be the bitwise xor of the remaining ones.
That is, if she chooses to forget vertex u_iu
i
, then her score is A_{u_1} \oplus A_{u_2} \oplus \ldots \oplus A_{u_{i-1}} \oplus A_{u_{i+1}} \oplus \ldots \oplus A_{u_{k}}A
u
1
⊕A
u
2
⊕…⊕A
u
i−1
⊕A
u
i+1
⊕…⊕A
u
k
. Here, \oplus⊕ denotes the bitwise xor operation.
Alice wants to maximize her score, and will always choose to forget a vertex optimally to achieve this.
What is Alice's expected final score?
Find the expected value modulo 10^9 + 710
9
+7.
That is, the expected value can be written as \frac{P}{Q}
Q
P
for two integers P, QP,Q such that \gcd(Q, 10^9 + 7) = 1gcd(Q,10
9
+7)=1; print the value of P\cdot Q^{-1} \pmod{10^9 + 7}P⋅Q
−1
(mod10
9
+7).
Input Format
The first line of input will contain a single integer TT, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains a single integer NN — the number of vertices of the tree.
The second line of each test case contains NN space-separated integers A_1, A_2, \ldots, A_NA
1
,A
2
,…,A
N
.
The next N-1N−1 lines describe the edges. The i^{th}i
th
of these lines contains two space-separated integers u_iu
i
and v_iv
i
, denoting an edge between u_iu
i
and v_iv
i
.
Output Format
For each test case, output on a new line Alice's expected final score.
Constraints
1 \leq T \leq 10^41≤T≤10
4
1 \leq N \leq 5\cdot 10^51≤N≤5⋅10
5
1 \leq A_i \leq 10^91≤A
i
≤10
9
The sum of NN over all test cases won't exceed 5\cdot 10^55⋅10
5
i
written on it.
Alice walks along this tree, starting at the root.
When she is at vertex uu:
If uu has no children, she stops.
Otherwise, suppose uu has cc children. She picks one of them at random (each one has a \frac{1}{c}
c
1
probability of being picked), and then moves to it.
Alice also has a score, defined as follows:
Let the vertices she visited be u_1, u_2, \ldots, u_ku
1
,u
2
,…,u
k
Then, she will forget exactly one of these kk vertices; and her score will be the bitwise xor of the remaining ones.
That is, if she chooses to forget vertex u_iu
i
, then her score is A_{u_1} \oplus A_{u_2} \oplus \ldots \oplus A_{u_{i-1}} \oplus A_{u_{i+1}} \oplus \ldots \oplus A_{u_{k}}A
u
1
⊕A
u
2
⊕…⊕A
u
i−1
⊕A
u
i+1
⊕…⊕A
u
k
. Here, \oplus⊕ denotes the bitwise xor operation.
Alice wants to maximize her score, and will always choose to forget a vertex optimally to achieve this.
What is Alice's expected final score?
Find the expected value modulo 10^9 + 710
9
+7.
That is, the expected value can be written as \frac{P}{Q}
Q
P
for two integers P, QP,Q such that \gcd(Q, 10^9 + 7) = 1gcd(Q,10
9
+7)=1; print the value of P\cdot Q^{-1} \pmod{10^9 + 7}P⋅Q
−1
(mod10
9
+7).
Input Format
The first line of input will contain a single integer TT, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains a single integer NN — the number of vertices of the tree.
The second line of each test case contains NN space-separated integers A_1, A_2, \ldots, A_NA
1
,A
2
,…,A
N
.
The next N-1N−1 lines describe the edges. The i^{th}i
th
of these lines contains two space-separated integers u_iu
i
and v_iv
i
, denoting an edge between u_iu
i
and v_iv
i
.
Output Format
For each test case, output on a new line Alice's expected final score.
Constraints
1 \leq T \leq 10^41≤T≤10
4
1 \leq N \leq 5\cdot 10^51≤N≤5⋅10
5
1 \leq A_i \leq 10^91≤A
i
≤10
9
The sum of NN over all test cases won't exceed 5\cdot 10^55⋅10
5
copy ques in notepad then do else you may get issue in understanding question
How many of you wanna learn JavaScript validation this Sunday will do one masterclass
Anonymous Poll
100%
Yes
0%
No
Whoever wants just message me @stockkida with your email ID 🙂 will add details to your calendar 🗓️
The way you guy's are voting looks like you guy's know everything n no need to consume more data
Java Hyd Team pinned «The way you guy's are voting looks like you guy's know everything n no need to consume more data»
Java Hyd Team
WHICH SUBJECT YOU WANT TO LEARN WITH US WITH A IMPLEMENTED PROJECT
Will cover core Java along with javascript validations this Sunday 😊
public class PalindromeNumber {
public static void main(String[] args) {
int x = -121;
if(isPalindrome(x)){
System.out.println(x + " is a Palindrome number");
}
else{
System.out.println(x + " is not a Palindrome number");
}
}
public static boolean isPalindrome(int x) {
if(x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int revertedNumber = 0;
while(x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
// When the length is an odd number, we can get rid of the middle digit by revertedNumber/10
// For example when the input is 12321, at the end of the while loop we get x = 12, revertedNumber = 123,
// since the middle digit doesn't matter in palidrome(it will always equal to itself), we can simply get rid of it.
return x == revertedNumber || x == revertedNumber/10;
}
}
public static void main(String[] args) {
int x = -121;
if(isPalindrome(x)){
System.out.println(x + " is a Palindrome number");
}
else{
System.out.println(x + " is not a Palindrome number");
}
}
public static boolean isPalindrome(int x) {
if(x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int revertedNumber = 0;
while(x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
// When the length is an odd number, we can get rid of the middle digit by revertedNumber/10
// For example when the input is 12321, at the end of the while loop we get x = 12, revertedNumber = 123,
// since the middle digit doesn't matter in palidrome(it will always equal to itself), we can simply get rid of it.
return x == revertedNumber || x == revertedNumber/10;
}
}
Given a valid (IPv4) IP address, return a defanged version of that IP address.
A defanged IP address replaces every period "." with "[.]".
Example 1:
Input: address = "1.1.1.1"
Output: "1[.]1[.]1[.]1"
Example 2:
Input: address = "255.100.50.0"
Output: "255[.]100[.]50[.]0"
Constraints:
The given address is a valid IPv4 address.
A defanged IP address replaces every period "." with "[.]".
Example 1:
Input: address = "1.1.1.1"
Output: "1[.]1[.]1[.]1"
Example 2:
Input: address = "255.100.50.0"
Output: "255[.]100[.]50[.]0"
Constraints:
The given address is a valid IPv4 address.
There is a programming language with only four operations and one variable X:
++X and X++ increments the value of the variable X by 1.
--X and X-- decrements the value of the variable X by 1.
Initially, the value of X is 0.
Given an array of strings operations containing a list of operations, return the final value of X after performing all the operations.
Example 1:
Input: operations = ["--X","X++","X++"]
Output: 1
Explanation: The operations are performed as follows:
Initially, X = 0.
--X: X is decremented by 1, X = 0 - 1 = -1.
X++: X is incremented by 1, X = -1 + 1 = 0.
X++: X is incremented by 1, X = 0 + 1 = 1.
Example 2:
Input: operations = ["++X","++X","X++"]
Output: 3
Explanation: The operations are performed as follows:
Initially, X = 0.
++X: X is incremented by 1, X = 0 + 1 = 1.
++X: X is incremented by 1, X = 1 + 1 = 2.
X++: X is incremented by 1, X = 2 + 1 = 3.
Example 3:
Input: operations = ["X++","++X","--X","X--"]
Output: 0
Explanation: The operations are performed as follows:
Initially, X = 0.
X++: X is incremented by 1, X = 0 + 1 = 1.
++X: X is incremented by 1, X = 1 + 1 = 2.
--X: X is decremented by 1, X = 2 - 1 = 1.
X--: X is decremented by 1, X = 1 - 1 = 0.
Constraints:
1 <= operations.length <= 100
operations[i] will be either "++X", "X++", "--X", or "X--".
++X and X++ increments the value of the variable X by 1.
--X and X-- decrements the value of the variable X by 1.
Initially, the value of X is 0.
Given an array of strings operations containing a list of operations, return the final value of X after performing all the operations.
Example 1:
Input: operations = ["--X","X++","X++"]
Output: 1
Explanation: The operations are performed as follows:
Initially, X = 0.
--X: X is decremented by 1, X = 0 - 1 = -1.
X++: X is incremented by 1, X = -1 + 1 = 0.
X++: X is incremented by 1, X = 0 + 1 = 1.
Example 2:
Input: operations = ["++X","++X","X++"]
Output: 3
Explanation: The operations are performed as follows:
Initially, X = 0.
++X: X is incremented by 1, X = 0 + 1 = 1.
++X: X is incremented by 1, X = 1 + 1 = 2.
X++: X is incremented by 1, X = 2 + 1 = 3.
Example 3:
Input: operations = ["X++","++X","--X","X--"]
Output: 0
Explanation: The operations are performed as follows:
Initially, X = 0.
X++: X is incremented by 1, X = 0 + 1 = 1.
++X: X is incremented by 1, X = 1 + 1 = 2.
--X: X is decremented by 1, X = 2 - 1 = 1.
X--: X is decremented by 1, X = 1 - 1 = 0.
Constraints:
1 <= operations.length <= 100
operations[i] will be either "++X", "X++", "--X", or "X--".
1480. Running Sum of 1d Array
Easy
5.7K
281
Companies
Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).
Return the running sum of nums.
Example 1:
Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].
Example 2:
Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].
Example 3:
Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]
Constraints:
1 <= nums.length <= 1000
-10^6 <= nums[i] <= 10^6
Easy
5.7K
281
Companies
Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).
Return the running sum of nums.
Example 1:
Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].
Example 2:
Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].
Example 3:
Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]
Constraints:
1 <= nums.length <= 1000
-10^6 <= nums[i] <= 10^6
Hi,Mam
As discussed I need candidate for application software Development
Android ios full stack developer ( Exp. 1-3yrs) (Male/Female)
Salry - 15k- 40k/month
Skills – Android ,ios,Java,Flutter,Laravel Node JS,React JS
Opening-1-2
Project Exp.- BBPS App,Cab Booking, Ecommerce Multivendor,Grocery App,Food Deliver
As discussed I need candidate for application software Development
Android ios full stack developer ( Exp. 1-3yrs) (Male/Female)
Salry - 15k- 40k/month
Skills – Android ,ios,Java,Flutter,Laravel Node JS,React JS
Opening-1-2
Project Exp.- BBPS App,Cab Booking, Ecommerce Multivendor,Grocery App,Food Deliver
*Hiring For Below Mentioned Profiles.*
*Java Developer* Experience - 3 to 5 years ? Notice Period - Max 30 Days.
*React Js Developer* Experience- 0 to 2 years.
*Location* -Pune.
Please share profiles
Kalyani Deshmukh
hr@bluepearlhealthtech.com
*Java Developer* Experience - 3 to 5 years ? Notice Period - Max 30 Days.
*React Js Developer* Experience- 0 to 2 years.
*Location* -Pune.
Please share profiles
Kalyani Deshmukh
hr@bluepearlhealthtech.com
Some more good opportunities on the way for mass Hiring ☺️ just have patience