using System.Collections.Generic;

class Solution
{
    // time O(n)
    public int[] PlusOne(int[] digits)
    {
        for (int i = digits.Length - 1; i >= 0; --i)
        {
            if (digits[i] < 9)
            {
                digits[i] = digits[i] + 1;
                return digits;
            }
            else
            {
                digits[i] = 0;
            }
        }

        // Array is initialized with zero values
        digits = new int[digits.Length + 1];
        digits[0] = 1;

        return digits;
    }
}

class Driver
{
    static void Main()
    {
        Test();
    }

    static void AssertEqual(int actual, int expected)
    {
        if (actual != expected)
        {
            throw new System.Exception(string.Format("Expected {0}, but got {1}", expected, actual));
        }
    }

    static void Test()
    {
        var solution = new Solution();
        int[] testcase1 = solution.PlusOne(new int[] { 1, 2, 3 });
        AssertEqual(testcase1[0], 1);
        AssertEqual(testcase1[1], 2);
        AssertEqual(testcase1[2], 4);
        AssertEqual(testcase1.Length, 3);
        
        int[] testcase2 = solution.PlusOne(new int[] { 4, 3, 2, 1 });
        AssertEqual(testcase2[0], 4);
        AssertEqual(testcase2[1], 3);
        AssertEqual(testcase2[2], 2);
        AssertEqual(testcase2[3], 2);
        AssertEqual(testcase2.Length, 4);

        int[] testcase3 = solution.PlusOne(new int[] { 9 });
        AssertEqual(testcase3[0], 1);
        AssertEqual(testcase3[1], 0);
        AssertEqual(testcase3.Length, 2);

        int[] testcase4 = solution.PlusOne(new int[] { 9, 9 });
        AssertEqual(testcase4[0], 1);
        AssertEqual(testcase4[1], 0);
        AssertEqual(testcase4[2], 0);
        AssertEqual(testcase4.Length, 3);
    }
}