ASU SoDA Coding Challenge VI Medium Question #3

On Sunday, November 24, 2019, I participated in the ASU SoDA Coding Challenge VI. The ASU Software Developer’s Association (SoDA) is a club that is dedicated to teaching aspiring programmers how to solve complex problems that will prepare them for industry. The club runs recruiting events, Hackathons, Interview Prep sessions, and other activities that I have personally found invaluable during my first semester at ASU. I would strongly recommend anyone with a remote interest in computer science to join the club.

The SoDA Coding Challenge had 15 questions which were divided into three categories of three questions based on their respective difficulty levels. The Easy Questions, the Medium Questions, and the Hard Questions were made available to the contestants through Google Forms, and participants would have proctors manually check their code to make sure their programs worked.

Medium Question #3 involves determining all numbers in a given range with no repeating digits. The question reads:

ASU SoDA Coding Challenge VI Medium Question 3: L and R
You have two integers l and r. Find an integer x which satisfies the conditions below:
l≤x≤r
l≤x≤r.
All digits of x are different.
If there are multiple answers, print ALL of them.
Input:
Two parameters l and r s.t. l < x < r.  l > 0, r < 10^5
Output:
If an answer exists, print all of them. Otherwise, print −1.
Test Cases:
input
121 130
output
123 124 125 126 127 128 129
input
98766 100000
output
-1

During the competition, there was a bit of confusion about this question because it was unclear whether all numbers in the range should be printed or just one number. It was officially decided that all numbers needed to be printed, so there is not much optimization to be done in this solution. Here’s my solution:

Solution #1: Basic Iteration Approach

We simply iterate through all integers from L to R and print all numbers with the given property. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 SoDA Coding Challenge VI Medium Problem #3
 https://docs.google.com/document/d/14sk0u9ZVM1rrIsSCSwIWesI1ks8BukFMaT-NlJCr6FQ/edit
 '''
 
 import time
 import sys
 for x in sys.stdin:
     a = map(int,x.split())
     l = a[0]
     r = a[1]
 
 def areDifferent(n):
     s = str(n)
     myDict = {}
     for x in s:
         if x in myDict:
             return False
         myDict.update({x : 1})
     return True
 
 def findNumber(l,r):
     found = False
     for x in range(l+1,r):
         if areDifferent(x):
             print x
             found = True
     if not found:
         print -1
 
 start = time.time()
 findNumber(l, r)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 -1
 --- 0.000833034515381 seconds ---
 
 for input of l = 98766, r = 100000
 ''' 

And with that, we’re done. To be honest, I was a bit disappointed with this question. A far more interesting version would be printing at least one number in the given range with the given property and increasing the bound on r. This would require a bit more work to solve. As the problem is written, I don’t believe it is possible to optimize the solution.

Thanks for reading! See you tomorrow.