ASU SoDA Coding Challenge VI Easy Question #5

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.

Easy Question #5 concerns determining the maximum product which can be formed by the digits of a number in a given range. The question reads:

ASU SoDA Coding Challenge VI Easy Question 5: Maximum numerical product
The problem is simple: Find the maximum possible product you can form using integers from 1,n.
Input: 
The only input contains the integer n (1≤n≤2⋅10^9).
Output: 
 Print the maximum product of digits among all integers from 1 to n
Test Cases:
input
390
 
output
216
 
input
7
 
output
7
 
input
1000000000
 
output
387420489
 
Note
In the first example the maximum product is achieved for 389 (the product of digits is 3⋅8⋅9=216). In the second example the maximum product is achieved for 7 (the product of digits is 7). In the third example the maximum product is achieved for 999999999 (the product of digits is 9^9) =387420489

I must confess, I am unsure whether my solution will get the correct answer for all possible inputs. Here is my solution:

Solution #1: Recursive First Digit Approach

We recursively find the number with the largest product by finding the largest possible left-most digit that can provide the maximum possible product and then calling the function for all digits to the right of the leftmost possible digit. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 SoDA Coding Challenge VI Easy Problem #5
 https://docs.google.com/document/d/1E_8BtPkGH5iQSBVOxr_lZpjrS5pToaWtDBS1WEZTxWw/edit
 '''
 
 import time
 import sys
 
 for x in sys.stdin:
     myInput = int(x)
 
 def maxProductDigits(n):
     if(n<=1):
         return 1
     if(n<10):
         return n
     power = 1
     while(power<=n):
         power*=10
     power/=10
     mySum = power
     if(2*power<=n):
         mySum = 3*power
         while(mySum<=n):
             mySum+=power
         mySum-=power
     v = mySum-1
     total = 1
     for x in str(v):
         total*=int(x)
     return(max(total,int(str(n)[0])*maxProductDigits(int(str(n)[1:]))))
 
 start = time.time()
 print maxProductDigits(myInput)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 472392
 --- 2.19345092773e-05 seconds ---
 
 for input of n = 900,000.
 ''' 

And with that, we’re done. Like I said, I am unsure whether this solution will always get the correct answer. It worked for all of the test cases on the day of the competition, and I am too lazy to rigorously check it, so I assume it works.

Thanks for reading! See you tomorrow.