We define a number to be special if it can be written as a ·197 + b ·232, for
some non-negative integers a and b. For example
•696 is special because it can be written as 0 ·197 + 3 ·232
•2412 is special because it can be written as 2412 = 4 ·197 + 7 ·232
•267 is NOT special. (Note that 267 = (−1) ·197 + 2 ·232, but this does
not count because −1 is a negative number.)
The goal of this problem is to write a DP algorithm Special(n):
•INPUT: a positive integer n
•OUTPUT: non-negative integers a and b such that n = a ·197 + b ·232,
or "no solution" is such a, b do not exists.
The Problem: Write an algorithm Special(n) that runs in O(n) time.
WHAT TO WRITE: write the five DP steps, including pseudocode for the
final algorithm. Note that your algorithm has to output the actual numbers