DEV Community

loading...

Days of Code [3]

Ronaldo Peres
・2 min read

Hi everyone,

Now I have this one:

"You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.
"

1 Example

  • Input: digits = [1, 2, 3]
  • Output: digits = [1, 2, 4]
  • Explanation: The array represents the integer 123.
  • Incrementing by one gives 123 + 1 = 124.
  • Thus, the result should be [1,2,4].

2 Example

  • Input: digits = [4,3,2,1]
  • Output: [4,3,2,2]
  • Explanation: The array represents the integer 4321.
  • Incrementing by one gives 4321 + 1 = 4322.
  • Thus, the result should be [4,3,2,2].

3 Example

  • Input: digits = [9,9,9]
  • Output: [1,0,0,0]
  • Explanation: The array represents the integer 99.
  • Incrementing by one gives 999 + 1 = 1000.
  • Thus, the result should be [1,0,0,0].

Constraints:

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9
  • digits does not contain any leading 0's.

Observations

Need to figure out how to solve this one without converting to int or long, since the array can pass the MaxValue, for example:

The int.Maxvalue = 2147483647;

We can have this input:

  • Input: digits = [9,8,7,6,5,4,3,2,1,0]

So if you think to solve:

  • Join the array and get a string "9876543210"
  • When parse it to int we get this, cause we pass the MaxValue:
    • System.OverflowException: 'Value was either too large or too small for an Int32.'

Here is my solution:

    public static class PlusOneArray
    {
        public static int[] PlusOne(int[] digits)
        {
            var numOfNine = GetNines(digits);
            if (numOfNine > 0)
            {

                if (digits.Length != numOfNine)
                {
                    digits[digits.Length - numOfNine - 1] += 1;
                }
                else
                {
                    digits[digits.Length - numOfNine] = 1;
                    var newDigits = new int[digits.Length + 1];
                    digits.CopyTo(newDigits, 0);
                    digits = newDigits;
                }

                int i = digits.Length - numOfNine;
                for (; i < digits.Length; i++)
                {
                    digits[i] = 0;
                }
            }
            else
            {
                digits[digits.Length - 1] = digits[digits.Length - 1] + 1;
            }

            return digits;
        }

        private static int GetNines(int[] digits)
        {
            int n = 0;
            for (int i = digits.Length - 1; i >= 0; i--)
            {
                if (digits[i] == 9)
                    n++;
                else
                    break;
            }
            return n;
        }
    }


Enter fullscreen mode Exit fullscreen mode

Also this is at my github:

Peres Github - Plus one

Happy coding!!

Discussion (2)

Collapse
seemstechies profile image
Sergey Inozemcev

I understand that you have some predicted conditions but it seems rather expensive to use stack for this sort of problem, because when you put some new value in front of array it is relocate all data in new disk space, much better to use List in this case. Also you can use BigNum object in real production.

Collapse
ronaldoperes profile image
Ronaldo Peres Author

Yes, I understand, but these are the constraints of the challenge.