Difficulty: Easy
Pre-requisite Knowledge: None
Core Idea/Tags: Math, implementation
Time Complexity:
\(O(T*N)\)
Quick Explanation:
Detailed Explanation:
For 0-9, its 0-9. From A onwards, its 10. This digit value can be found by subtracting suitable values from ASCII values. (subtract 48 for 0-9, 55 for A-Z since A is 65 and we need 10).
Take a number "abc" in base X. As mentioned in question, the number in base 10 is a*(X^2) + b*(X) + c.
If X is odd, the parity of the number is dependent on each of the term's multiplicand other than X i.e., the digits "a,b,c" itself. Here, parity of each digit will determine parity of each of the terms. Thus, we need number of odd digits(rather than sum of all digits, since we require only the parity finally). If there are odd no. of odd terms, then its odd, else even. This can be found by traversing through the string once, which is O(N).
If X is even, all terms except "c" would be even. Thus, what determines the parity of the number is the parity of the last digit, which can be found when we traverse through the array in O(1).
What's left now is to find the no of odd and even bases. We can find the no of even terms between any two numbers as we find no of multiples of 2. Then, subtract it from total terms so as to get no of odd terms. This is an O(1) task, which I prefer to leave it to the reader as a simple exercise.
Now, the answer is parity of [(no of odd bases)*(parity of term if odd base) + (no of even bases)*(parity of term if even base)] since the math behind every even/odd base would be same as explained above.
Solution Links: