PROBLEM LINK:
Author: Ajay Sharma
Tester: Manisha Singh
Editorialist: Akshay Sharma
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Arrays
PROBLEM:
Jerseys are to be printed for every number between A and B (including A and B) with every number appearing on exactly one jersey. By mistake, one particular number got printed twice resulting one number not printed on the jersey as total number of jerseys remained same. Find that missing number.
QUICK EXPLANATION:
To find the missing number in a continuous array between two numbers A and B provided only one number is missing and one number is twice in the array so that size of array are B-A+1.
EXPLANATION:
Initialize a variable with first input which is the number of test cases.
For each test case we initialized A and B with next set of inputs. A and B are the numbers between which jerseys are to be printed including A and B.
For each test case we declared an array of size N=B-A+1 and initialized it to 0.
Now for every element in the third line (N number of elements) we input element as num and incremented the array value by 1(initially initialized to 0) where array index = num-A.
We used num-A as the index so that all the numbers, initially between A and B, gets scaled to a number between 0 to N-1 (size remains same i.e. N).
Now, we can easily see that the array we made has value=1 corresponding to each element between A and B except the one that is missing has value=0 and one who is doubles has value=2.
Now as we have tell the missing number, we search for the array index whose value=0.
Finally, we printed the number where value=0, scaling it again, i.e. adding A to it again. Number +A is the missing number.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.