Problem: Separate the Numbers

*Difficulty: Easy

Problem:
separate-the-numbers-english

Approach:
Here’s how I did it, and I think example is the best way to explain it:
Example:
s = 1011121314
Start with first number = 1, next is 0, False
Start with first number = 10, next is 11, next is 12, …..
Eventually, return True
The maximum length of first number will be equal len(s) // 2 (if length s is even), or len(s) // 2 + 1 (length s is odd)
Let’s take another example:
10000001000001
First number: 1, next 0 => False
First number: 10, next 00=> False
First number: 100, next 000=>False
First number: 1000. next 000=>False
….
First number:1000000 next 1000001 => True
Hope you get the idea :>

Implementation: Python 3

def is_beautiful(number):
    if number == '' or number[0] == '0' or len(number) <= 2:
        return [False] 
    bound = len(number) // 2
    start_length = 1
    while start_length <= bound:
        first_str = number[:start_length]
        first_int = int(first_str)
        i = start_length
        try:
            while i < len(number):
                next = next_str(i, first_str, first_int, number)
                if next is None:
                    break
                else:
                    changed = False
                    next_1, next_2 = next
                    if int(next_1) == first_int+1:
                        first_str = next_1
                        first_int = int(next_1)
                        i += len(next_1)
                        changed = True 
                    else:
                        if next_2:
                            if int(next_2) == first_int+1:
                                first_str = next_2
                                first_int = int(next_2)
                                i += len(next_2)
                                changed = True 
                    # cant found next number 
                    if not changed:
                        break
                    # check out of bound 
                    if i > len(number):
                        break
                    # all numbers statisfy the condition
                    if i == len(number):
                        return True, number[:start_length]
        except Exception:
            pass
        start_length += 1
    return [False]

def next_str(i, first_str, first_int , number):
    # get the next number 
    # check if it has equal or longer length 
    # return two next, but only one of them is usable 
    next_1 = ""
    next_2 = ""
    if i < len(number):
        if number[i] == '0':
            return None 
        else:
            if i + len(first_str) <= len(number):
                next_1 = number[i:i+len(first_str)]
            if i + len(first_str) + 1 <= len(number):
                next_2 = number[i:i+len(first_str)+1]
            return next_1, next_2
    return None

def main():
    t = int(input())
    for _ in range(t):
        number = str(input().strip())
        result = is_beautiful(number)
        if result[0]:
            print('YES', result[1])
        else:
            print('NO')

if __name__ == '__main__':
    main()
Advertisements