PROC-X.com

1. Translate the numbers to an array of integer to avoid stack overflow
2. Use while to control flow once the iteration times are unknown
3. Apply % and \ to retrieve digits from a integer
4. Be careful of the direction of the iteration

• Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

def rev_int(a):
    negative = False
    result = 0
if a == 0:
return a
if a < 0:
        negative = True
        a = -a
while a > 0:
        result = result*10 + a%10
        a /= 10
if negative:
return -result
return result

if __name__ == "__main__":
print rev_int(123)
print rev_int(-4124324)

• Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

class multiply:
def mul(self, int1, int2):
        a = self.toArray(int1)
        b = self.toArray(int2)
        c = [0]*(len(a) + len(b))
        d = [0]*(len(a) + len(b))
for i in range(len(a)):
for j in range(len(b)):
                p = a[i] * b[j]
                c[i+j+1] += p
        rem = 0
for i in reversed(range(len(c))):
            c[i] += rem
            carry = c[i]%10
            rem = c[i]/10
            d[i] = carry
return self.toInt(d)

def toArray(self, n):
        result = []
while n > 0:
            a = n%10
            result.append(int(a)) # a is possibly a long type given the value of n
            n = n/10
return [x for x in reversed(result)]

def toInt(self, a):
        y = 0
for i in range(len(a)):
            mul = 10**( len(a)-1-i )
            y += a[i]*mul
return y

if __name__ == "__main__":
    a = multiply()
# Testcase1
print a.mul(9934248, 983204442)
print 9934248*983204442
# Testcase2
print a.mul(1, 2)

• Valid Number

Validate if a given string is numeric.
Some examples:
“0” => true
“ 0.1 “ => true
“abc” => false
“1 a” => false
“2e10” => true

def valid_num(a):
try:
        a = float(a)
except:
return False
return True

• Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = “11”
b = “1”
Return “100”.

def bin_add(a, b):
if len(a) < len(b):
        a, b = b, a
    c = [0]*len(a)
    b = '0'*(len(a)-len(b)) + b

    carry = 0
for i in range(len(a)):
        index = -i - 1 # from the right to the left
        c[index] = carry + int(a[index]) + int(b[index])
        carry = 0
if c[index] == 2:
            c[index] = 0
            carry = 1
if i == len(a) - 1:
                c.insert(0, 1)
return ''.join([str(x) for x in c])

if __name__ == "__main__":
print bin_add('1', '1001')
print bin_add('11', '1')
print bin_add('0', '0')

• Plus one

def plus_one(a):
# Error case and bad case
if not isinstance(a, list) or len(a) == 0:
raise ValueError
# Normal case
for i in reversed(range(len(a))):
if a[i] == 9:
            a[i] = 0
else:
            a[i] += 1
return a
# Special case
    a.insert(0, 1)
return a

if __name__ == "__main__":
    testcase1 = [1, 2, 3, 4]
print plus_one(testcase1)
    testcase2 = [8, 9, 9, 9]
print plus_one(testcase2)
    testcase3 = [9, 9, 9, 9]
print plus_one(testcase3)
    testcase4 = 0
print plus_one(testcase4)

• Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, …
1 is read off as “one 1” or 11.
11 is read off as “two 1s” or 21.
21 is read off as “one 2, then one 1” or 1211.
Given an integer n, generate the nth sequence.

def read(a):
# The array for counter and value
    current = [0, 10]
    result = []
for i in range(len(a)+1):
if i == len(a):
            result += current
return result[2:] # return result from the last loop
if a[i] == current[1]:
            current[0] += 1
else:
            result += current
            current[1] = a[i]
            current[0] = 1
        carrier = a[i]

def cnt_say(n):
# Set the initial seed
    result = [1]
for i in range(n):
        result = read(result)
# Return the result as a string
return ''.join(str(x) for x in result)

if __name__ == "__main__":
for i in range(10):
print cnt_say(i)

• Read Numbers

1 -> one
100 -> one hundred
500234 -> five hundred thousand two hundred thirty four
1232232 -> 1 million two hundred ….

def read_piece(s):
if len(s) < 2:
return s
return s[0] + ' hundred ' + s[1:]

def read(s):
    alen = len(s)
    read2 = {0: '', 1: 'thousand', 2: 'million', 3: 'billion', 4: 'trillion'}
    b = []
    result = []
while alen > 0:
        low = max(0, alen-3)
        high = alen
        b.append(s[low: high])
        alen -= 3

for i, x in enumerate(reversed(b)):
        index = len(b) - i - 1
        result += [read_piece(x), read2[index]]
return ' '.join(n for n in result)

Read more →