Jarvis and Numbers -Practice Problem from Hackerearth and solution using python 2.7.6

Problem Statement:

After defeating Mandarin in Iron man 3, Jarvis is most of time free and now he has started playing with numbers. Jarvis being an AI (Artificial Intelligence) solves almost all the riddle given by Tony Stark very quickly. This time Tony gave him a problem about base conversion’s but the problem statement given by Tony seems to be confusing and Jarvis asked for Help! Problem Statement – “123 when converted in base 16, it consist of two digits 7 and 11 so the sum of the numbers is 18,(For Given N) Find denominator of average(irreducible form) of sum of all the numbers formed on conversions from base 2 to N-1”.

Can you help Jarvis?

Input:

First line will have the number of test case (t) and then t subsequent lines will contain a number $N$.

Output:

For every test case, give answer in new line.

Constraints:
$T<10$, 

3 <= N <=1000

Programming using python 2.7.6:

We need to first understand what is irreducible fraction. Let's take an example 26/13, where numerator is 26 and denominator is 13. The result of 26/13 is 2, which can be further written as 2/1. 

Now let's take another example: 21/18. In this fraction both numerator and denominator can be divisible by 3, which further reduced to 7/6. Now we can not further divide numerator with denominator to get integer number. In both the cases the irreducible fraction will be 2/1 and 7/6 respectively.

In the above problem statement , we need to derive the sum of all the numbers with respect to each base value of given input number and then divide by number of base value which we calculated i.e 2 to N-1. That means for given input number we can have N-2 base values (since we are only starting from base 2 to N-1).

So we simplified our understanding about the problem to some extent :)

In python , we can use Fraction instance to get irreducible fraction by importing fractions module.(You can refer Numeric and Mathematical modules section from python documentation https://docs.python.org/2/library/fractions.html#fractions.Fraction for more details.)

Code in Python 2.7:

from fractions import Fraction

finalresult = []

# Function to get differnt base value numbers for given input and return the

# result in list

def getDifferentBase(num,base):

    outputRes = []

    if num <= 0:

        return 0

    else:

        while num:

            outputRes.append(num % base)

            num/=base

        return outputRes[::-1]

T = int(raw_input())

while T: # For each test case iterate and get user input numeric value

    N = int(raw_input())

    Sum = 0 # Get sum of all the numbers formed on conversions from base 2 to N-1

    for base in range(2,N,1):

        Sum += sum(getDifferentBase(N, base))

    finalresult.append(Fraction(Sum,N-2).denominator) # Get the denominator of average(irreducible form)

    T -=1

   

for res in finalresult: print res