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 #2 concerns really big numbers, or numbers which have a large difference with the sum of their digits. The question reads:
ASU SoDA Coding Challenge VI Medium Question 2: Really Big Numbers Problem
Ivan likes to learn different things about numbers, but he is especially interested in really big numbers. Ivan thinks that a positive integer number x is really big if the difference between x and the sum of its digits (in decimal representation) is not less than s. To prove that these numbers may have different special properties, he wants to know how rare (or not rare) they are — in fact, he needs to calculate the quantity of really big numbers that are not greater than n.
Ivan tried to do the calculations himself, but soon realized that it's too difficult for him. So he asked you to help him in calculations.
Input:
The input consists of two integers, n and s
Output:
Print one integer — the quantity of really big numbers that are not greater than n.
Test Cases:
input
12 1
output
3
input
25 20
output
0
input
10 9
output
1
Note
In the first example numbers 10, 11 and 12 are really big.
In the second example there are no really big numbers that are not greater than 25 (in fact, the first really big number is 30: 30 - 3 ≥ 20).
In the third example 10 is the only really big number (10 - 1 ≥ 9).
My solution for this problem is probably not as optimized as it could be. Here’s my solution:
Solution #1: Lower Bound Approach
We can observe that for any given difference s, there is a smallest number x such that for all values greater than or equal to x, x-sum(x) >= s. Thus, it suffices to count all really big numbers less than or equal to this lower bound and then count the numbers between the lower bound and n.
To find the lower bound, it suffices to check whether x is a really big number and whether x + 9*num(x) < ten(x) where num(x) is the number of digits in x and ten(x) is the smallest power of 10 which is greater than x. Doing this for every number, we can easily find the lower bound. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
SoDA Coding Challenge VI Medium Problem #2
https://docs.google.com/document/d/14sk0u9ZVM1rrIsSCSwIWesI1ks8BukFMaT-NlJCr6FQ/edit
'''
import time
import sys
from numpy.f2py.auxfuncs import throw_error
for x in sys.stdin:
try:
a = map(int,x.split())
n = a[0]
s = a[1]
except:
throw_error("Incorrect input format.")
def sumDigits(a):
total = 0
for x in str(a):
total+=int(x)
return total
def numDigits(i):
return len(str(i))
def power(i):
power = 1
while(power<=i):
power*=10
return power
def reallyBigQuantity(n,s):
total = 0
i = 1
while(i<=n):
if i-sumDigits(i) >=s:
total+=1
if i-numDigits(i)*9>=s and i+numDigits(i)*9<=power(i):
total+=n-i
break
i+=1
return total
start = time.time()
print reallyBigQuantity(n, s)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
0
--- 5.69820404053e-05 seconds ---
for input of n = 25, s = 20.
'''
And with that, we’re done. There may be more efficient ways to search for the upper bound, but this was the quickest method I could think of.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 