MGMTX - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice

Author: Shril

Tester: Janvi

Editorialist: Shril

DIFFICULTY:

Cakewalk

PREREQUISITES:

Basic Math and knowledge of Kaprekar numbers (Kaprekar number - Wikipedia)

PROBLEM:

Given a number, find the turns until which it gets converted to a number which repeats itself.

QUICK EXPLANATION:

As the length of the numbers can be maximum of 8. We can apply brute force and keep storing numbers that we acquire and count the turns.

EXPLANATION:

As the series always terminates fairly quickly even for large numbers, we can apply brute force method.

We need to take the number and sort it’s digits in ascending and descending order to get the maxa and mina respectively, which can be done in O(dlog(d)) time (where d are the digits of the number).

Store this difference in an array and check everytime if the number is repeating or not, takes O(k) time (where k is the size of the array).

The iterations may vary but it can be proved that they won’t be more than the number n.

So, the overall complexity becomes O(dlog(d) + m) (where m<n).

SOLUTIONS:

Setter's Solution 

def get_num(N):
    number=list(str(N))
    number.sort()
    smallest = ''
    largest = ''
    for i in range(0,len(number)):
        smallest+=number[i] 
        largest+=number[len(number)-1-i]
    small_num = int(smallest)
    large_num = int(largest)
    return [small_num,large_num]

for _ in range(int(input())):
    N = int(input())
    dic={}
    if(N not in dic):
        dic[N]=1 
    count=0 
    flag=0 
    check = N
    while(flag!=1):
        ans = get_num(check)
        answer = ans[1]-ans[0]
        if(answer in dic):
            flag=1
        else:
            dic[answer]=1 
            count+=1 
            check=answer 
    print(count)