Once upon a times , there lived King Nihal who hated odd counting . He has received…
- User
Once upon a times , there lived King Nihal who hated odd counting . He has received various gifts from different kings of other kingdoms on his birthday. There is one enemy king , and to make our king angry he will send odd number of gifts . As a sincere minister , its your task to find the enemy kingdom. Input
T- number of test cases
N- number of gifts he received
N inputs each corresponding to the Kingdom from which the gift has come.
The gift number represents the Id of kingdom from which he received the gift
Output
Id of enemy kingdom
constraints 0<T<11 0<N ≤ 10^6 0<id<10^4
Eg.
2
7
1 1 2 2 2 2 3
5
4 4 4 7 7
Output
3
4
Explanation
In the second test case he got 5 gifts from 2 kingdoms( id 4 and id 7 ), now kingdom 4 sends him odd number of gifts (3) so we find out that kingdom id 4 is his enemy.
SAMPLE INPUT 2
7
1 1 2 2 2 2 3
5
4 4 4 7 7
SAMPLE OUTPUT 3 4
Assistant
We need to read the problem carefully. The problem: "King Nihal hated odd counting. He has received various gifts from different kings of other kingdoms on his birthday. There is one enemy king, and to make our king angry he will send odd number of gifts. As a sincere minister, its your task to find the enemy kingdom."
So essentially, we have N gifts each labeled with an id (kingdom). All kingdoms send gifts. Among them, there is exactly one enemy kingdom, which sends an odd number of gifts. All other kingdoms send even numbers of gifts? Let's read: "He has received various gifts from different kings of other kingdoms on his birthday. There is one enemy king, and to make our king angry he will send odd number of gifts." It implies that the enemy kingdom sends an odd number of gifts, whereas the other (friendly) kingdoms send even numbers? Not explicitly, but from the sample: In the first test case, N=7, ids: 1,1,2,2,2,2,3. Counts: id1:2 (even), id2:4 (even), id3:1 (odd). So enemy is id3. In second test case: ids: 4,4,4,7,7 => id4:3 (odd), id7:2 (even). Enemy is id4. So yes, we need to find the id that appears an odd number of times, given that exactly one id will have odd frequency? The problem says "There is one enemy king" implies exactly one kingdom sends odd number. So we can assume that among the ids, exactly one id occurs an odd number of times, all others occur even times. But we need to confirm: Could there be a case where multiple odd? The problem statement says "There is one enemy king, and to make our king angry he will send odd number of gifts." It doesn't say others will send even, but it is implied that the king hates odd counting, so enemy purposely sends odd. But perhaps other kingdoms may also send odd? However typical similar problems (like "find the number that appears odd times" and others even) is like "odd one out" or "lonely integer". Usually it's exactly one odd. However constraints are up to 10^6 N, ids up to 10^4. We can use a frequency array of size 10001 (since id < 10^4, but id >0). Or we can use XOR trick: if we XOR all ids, but careful: XOR works if all others appear even times and one appears odd times, then XOR of all numbers yields the one with odd count. But wait: XOR trick works if each number appears even number of times except one that appears odd number of times. XOR of a number with itself even times cancels to 0, odd times leaves itself. So we can simply XOR all the ids to get the enemy kingdom id. This is efficient O(N) time and O(1) memory. However, is it guaranteed that all other ids appear even times? The statement: "He has received various gifts from different kings of other kingdoms on his birthday. There is one enemy king, and to make our king angry he will send odd number of gifts." It doesn't explicitly say that friendly kings always send even numbers. But from sample, it holds. Usually in such problems, they'd specify "All other kingdoms send even number of gifts" or something, but they didn't. However, the typical interpretation is exactly one kingdom sends odd number, others send even. Let's read again: "King Nihal who hated odd counting. He has received various gifts from different kings of other kingdoms on his birthday. There is one enemy king , and to make our king angry he will send odd number of gifts . As a sincere minister , its your task to find the enemy kingdom." So the enemy king is the one who sends odd number to make the king angry. The king hates odd counting, so enemy deliberately sends odd number. The other kings presumably don't want to anger the king, so they'd send even numbers. So yes, it's implied that all other kingdoms send even numbers. So we can safely use XOR.
But consider if multiple kingdoms could send odd? The problem says "there is one enemy king", so exactly one. So XOR works.
But what about the input format? Let's parse. It says:
Input T- number of test cases N- number of gifts he received N inputs each corresponding to the Kingdom from which the gift has come. The gift number represents the Id of kingdom from which he received the gift
Output Id of enemy kingdom
Constraints: 0<T<11 0<N ≤ 10^6 0<id<10^4
Sample Input: 2
7
1 1 2 2 2 2 3
5
4 4 4 7 7
Sample Output: 3 4
Note: There are blank lines in sample but actual input may not have them. We'll just read integers.
So solution: For each test case, read N, then read N integers. Compute XOR of all integers. Print the result.
However, is it possible that the enemy kingdom appears multiple times? Yes, odd count could be 1,3,5,... XOR works regardless.
But is there any twist? The problem says "King Nihal hated odd counting." Maybe he hates odd numbers in general. But enemy sends odd number of gifts to anger him. So we need to find the id which sent odd count.
Potential pitfalls: id can be zero? Constraints say 0<id<10^4, so id is positive integer from 1 to 9999? Actually says 0<id<10^4, so id could be 1 to 9999 inclusive? It says 0 < id < 10^4, so id >=1 and <=9999. So no zero ids. So XOR will yield id if it's odd count. But what if all ids appear even times? That would mean no enemy? But problem says there is exactly one enemy, so not.
Edge case: N could be 0? But constraints say 0<N? Actually 0<N ≤ 10^6, so N>0. So at least one gift.
Multiple test cases up to 10. So total N across tests could be up to 10^6 * 10 = 10^7, which is okay.
So we can implement with XOR.
But we must be careful about reading input fast because N could be large. Use sys.stdin.read() to read all ints at once.
Implement: read all integers from sys.stdin. First integer T. Then for each test case, read N, then read N integers. Compute XOR.
Output each result on separate line.
Testing with sample: Input: 2 7 1 1 2 2 2 2 3 5 4 4 4 7 7 => XOR1: 1^1=0, then ^2^2^2^2 = 0, then ^3 = 3. Output 3. XOR2: 4^4=0, ^4=4, ^7=3? Wait compute: 4 XOR 4 = 0, XOR 4 = 4, XOR 7 = 3? Actually 4 XOR 7 = 3, then XOR 7 = 4? Let's recalc properly: start 0; first 4: 0^4=4; second 4: 4^4=0; third 4: 0^4=4; fourth 7: 4^7=3; fifth 7: 3^7=4. So result 4. Yes.
So XOR works.
But is there any scenario where XOR fails? Only if there is more than one odd occurrence, or if some numbers appear even times but some appear odd times but multiple odds. But as per problem, only one odd.
Alternative: Use frequency array of size 10001, count mod 2, but XOR is simpler.
Thus solution: read T, loop.
We must be cautious about input format: In sample there are blank lines, but we'll ignore them by reading ints.
Implementation details: Use sys.stdin.buffer.read() to read all bytes, split, map to ints. Then iterator.
Pseudo:
import sys
def main(): data = list(map(int, sys.stdin.buffer.read().split())) it = iter(data) t = next(it) out_lines = [] for _ in range(t): n = next(it) xor = 0 for i in range(n): xor ^= next(it) out_lines.append(str(xor)) sys.stdout.write("\n".join(out_lines))
if name == "main": main()
That's it.
But I should also consider if the input could be given with each test case separated by newlines and spaces, but it's fine.
Now, note constraints: T<11, so at most 10. N up to 10^6 per test, so total up to 10 million numbers. Reading all into memory as ints could be up to 10 million integers, each Python int uses ~28 bytes, so ~280 MB, which might be borderline but maybe okay? Actually 10 million integers as Python ints is large (approx 280 MB). That could exceed memory limit if memory is 256 MB? Not sure. Better to use a generator reading from iterator without converting all to list at once? Actually sys.stdin.buffer.read().split() returns list of bytes strings, not ints. If we map to ints with map, but if we convert to list, that also stores all ints. But we can process as we read using iterative reading. However we need to read all input quickly. Option: use sys.stdin.buffer.read().split() yields a list of bytes, each representing a number. That list will have total number of tokens = 1 + sum(1+N) across tests. For worst-case T=10, each N=10^6, so tokens = 10*(1+1e6) + 1? Actually each test has N and N numbers, plus T at start. So total tokens = T + sum_{tests}(1+N) = 10 + 10*(1+1e6) = 10 + 10 + 10e6 = 10000020? Actually 10 tests: each test has 1 (for N) + 1e6 numbers = 1,000,001 tokens, so 10 * 1,000,001 = 10,000,010 tokens, plus T=10 => 10,000,020 tokens. That's about 10 million tokens. The list of bytes strings: each token is a small bytes object (like b'1234'), overhead maybe ~50 bytes each, so memory could be ~500 MB, which is too high. So we should avoid storing all tokens at once.
We can instead read line by line using sys.stdin.buffer.readline. Because N can be up to 10^6, we can read the line containing the numbers? But note that the numbers might be on multiple lines? The input specification: after N, there are N inputs each corresponding to the Kingdom from which the gift has come. It doesn't say they are all on one line; they could be spread across lines. In sample, they are given on separate lines? Actually sample:
2
7
1 1 2 2 2 2 3
5
4 4 4 7 7
So for test case 1, after 7, the next line contains 7 numbers. That's typical: all numbers may be on one line, but N up to 10^6, one line with 1e6 numbers might be huge (line length ~ 5 million characters) but that's okay? But typical programming problems may have them space-separated across multiple lines. Usually they allow lines to be arbitrarily long, but some judges limit line length? However we cannot rely on all numbers being on a single line. Safer to read numbers one by one using split over the entire input but streaming. But we need an efficient method that doesn't blow memory.
We can use an iterator over sys.stdin.buffer.read().split() but that loads all tokens into memory as bytes. That could be too much. Alternative: we can implement a fast scanner that reads chunks and yields ints on the fly. But for Python, typical solution for large input is to use sys.stdin.buffer.read().split() and it often passes even for 10^6 tokens? Let's calculate: 10 million tokens, each token is a bytes object. On a 64-bit Python, a bytes object overhead is about 33 bytes plus the length of the data? Actually each bytes object is an immutable object with a header and the data. For a small number like '1234', it's 4 bytes of data. So overhead maybe ~37 bytes? So 10 million tokens * 37 = 370 MB. Plus list overhead: the list itself holds references (8 bytes each) => 80 MB. Total maybe 450 MB, which may exceed typical memory limit (256 MB). So risk.
Better to use a generator that reads lines and splits them as we go. For each test case, we need to read N integers. We can read lines and split them until we have accumulated N numbers. This is a standard approach: for each test case, read N, then initialize count=0, while count < N: read a line, split into tokens, for each token convert to int and process. This avoids storing all tokens at once. Complexity is O(total input size) and memory is limited to a line's buffer.
We must be careful about blank lines. In sample, there are blank lines. So we may need to skip empty lines. Using line reading, we can read line, if line.strip() is empty, skip and continue reading. That's fine.
Implementation:
import sys
def main(): data = sys.stdin.buffer t_line = '' while t_line.strip() == '': t_line = data.readline() T = int(t_line) out = [] for _ in range(T): # read N, skipping empty lines line = '' while line.strip() == '': line = data.readline() N = int(line) xor = 0 remaining = N while remaining > 0: line = data.readline() if not line: break # but shouldn't happen parts = line.split() for part in parts: if remaining == 0: break xor ^= int(part) remaining -= 1 out.append(str(xor)) sys.stdout.write("\n".join(out))
Edge Cases: If after reading N, the numbers might be spread across lines; our loop reads until we have N ints, ignoring line boundaries. Good.
But we also need to handle the case where there may be extra whitespace after the last number of a test case. That's fine because we read until we have N numbers; any extra numbers would be part of next test case? But input should not have extra numbers. So it's fine.
Alternatively, we could use the XOR trick with frequency array of size 10001 to be safe and still memory efficient, but we would still need to read numbers. But XOR is simpler.
Thus final solution: as above.
Now ensure we comply with constraints: id<10^4, so XOR result is within that range.
Complexities: O(total numbers) time, O(1) extra memory (besides output).
We'll provide explanation and code.
But there's a potential nuance: The problem says "King Nihal hated odd counting." Possibly we need to find the enemy kingdom by looking for the id that appears odd number of times. But what if there are multiple odd counts? Not allowed per statement.
One could also use a dictionary or counter, but XOR is optimal.
Thus answer is straightforward.
Now write final answer.
Also note: Input may have T on first line, then each test case: N on its own line, then the N ids on possibly multiple lines. We'll handle as described.
Let's produce final solution.
But wait: There is sample input with blank lines. Our code that skips empty lines for N and T should handle that. However for reading numbers, we don't skip empty lines because we will encounter empty lines as line = data.readline() which may be blank. In that case line.split() returns empty list, and we continue looping while remaining > 0. So it's fine; we just read another line. So blank lines are effectively skipped.
Thus solution is ready.
Now finalize.
We should also mention that we assume exactly one odd count.
Now produce final answer with code and explanation. We need to find the enemy kingdom – the only one that sent an odd number of gifts. All other kingdoms sent an even number.
The XOR operation cancels numbers that appear an even number of times, leaving the one with odd frequency.For each test case, we read
Nand thenNintegers, XOR them all together, and output the result.This works in O(total numbers) time and O(1) extra memory.
import sys def main(): data = sys.stdin.buffer # read number of test cases, skipping empty lines line = b'' while line.strip() == b'': line = data.readline() T = int(line) out = [] for _ in range(T): # read N, skipping empty lines line = b'' while line.strip() == b'': line = data.readline() N = int(line) xor = 0 needed = N while needed > 0: line = data.readline() # if input ends prematurely (should not happen) if not line: break for token in line.split(): if needed == 0: break xor ^= int(token) needed -= 1 out.append(str(xor)) sys.stdout.write("\n".join(out)) if __name__ == "__main__": main()