parikshan

plus-one

Difficulty: Easy  ·  Topic: Math, Matrix & Heaps  ·  Practice it on parikshan: /practice/plus-one/start

The story

A backend engineer at Stripe inherits a service that increments transaction sequence numbers. The numbers are stored as arrays of decimal digits, not as integers, for one reason: the sequence is unbounded, the language used does not have arbitrary-precision integers everywhere, and the team decided long ago that any arithmetic on money or identifiers must avoid floating-point conversion. The job for today is small: add one to a digit array. [1, 2, 3] becomes [1, 2, 4]. [9, 9, 9] becomes [1, 0, 0, 0]. The function gets called millions of times per minute.

That is plus-one. It looks trivial, but the discipline it teaches, carry propagation on digit arrays, shows up everywhere money, OCR, and version numbers are handled correctly.

What's actually being asked

You are given a non-negative integer represented as an array of decimal digits, most-significant first. Add one to the integer and return the resulting digit array. The leading digit is non-zero unless the number itself is zero.

The naive approach

Convert the array to a string, parse to an integer, add one, then split back into digits. In Python this is three lines and it works. In a language without arbitrary-precision integers, it silently overflows the moment the input crosses the integer ceiling. The naive answer is correct in toy languages and a landmine in production. Worse, it teaches none of the technique.

The key insight

Addition propagates carry from right to left. Adding one is the smallest possible addition, so the carry is at most one bit. Walk the digits from right to left. Every time you find a 9, set it to 0 and continue (the carry keeps propagating). The moment you find a digit less than 9, increment it and stop. If you fall off the left end, every digit was a 9; prepend a 1.

You do not even need a carry variable. The act of setting a 9 to 0 is the carry. The act of incrementing a digit less than 9 consumes the carry. One loop, one branch.

Step-by-step approach

  1. Set i = n - 1 (the rightmost index).
  2. While i >= 0:
    • If digits[i] < 9, increment digits[i] and return.
    • Otherwise set digits[i] = 0 and decrement i.
  3. If the loop ends without returning, every digit was 9. Prepend 1 to the array of zeros and return.

Worked example

digits = [9, 9, 9]
  • i=2, digits[2]=9, set to 0, i=1. Array: [9, 9, 0].
  • i=1, digits[1]=9, set to 0, i=0. Array: [9, 0, 0].
  • i=0, digits[0]=9, set to 0, i=-1. Array: [0, 0, 0].
  • Loop ended. Prepend 1. Result: [1, 0, 0, 0].

Now try [1, 2, 9]:

  • i=2, digits[2]=9, set to 0, i=1. Array: [1, 2, 0].
  • i=1, digits[1]=2 (less than 9), increment to 3 and return. Result: [1, 3, 0].

The carry stopped the moment it hit a digit with room to absorb it.

Complexity

  • Time: O(n) worst case (all nines), O(1) amortised for typical inputs that have a non-nine somewhere on the right.
  • Space: O(1) in place, or O(n) when you have to prepend on the all-nines case.

Common pitfalls

  • Adding a carry variable: redundant. The +1 is one-shot. Carry is at most one and is naturally absorbed by the first digit that is not 9.
  • Walking left to right: you would have to walk twice, once to find where to put the carry and once to apply it. The right-to-left walk does both in one pass.
  • Forgetting the prepend: easy to miss the all-nines case if you have not tested [9].
  • Converting through int and back: works in Python, breaks in Java/C for 64-bit overflow, breaks everywhere for arbitrarily long inputs. The whole reason the problem represents the number as an array is to avoid that conversion.

Where this shows up in the enterprise

  • Stripe, Adyen, PayPal, Square: every payment processor stores money as integer cents (or thousandths), never as floats. Float arithmetic on money is the costliest class of production bug, since rounding errors accumulate across thousands of transactions. Adding to an amount is digit-array addition.
  • OCR pipelines (Tesseract, Google Cloud Vision): receipts and forms are scanned into digit arrays before they are interpreted as numbers. Incrementing a serial number on a scanned form is plus-one on those digits.
  • Version-number parsers: semver bumps and build-number increments often walk digit by digit. 1.2.99 to 1.3.0 is plus-one at the patch level with a carry into minor.
  • Cryptographic counters: AES-GCM and ChaCha20 both use a counter that increments per block. The counter is treated as a byte array because it can be larger than any native integer.
  • Database row IDs in Spanner and CockroachDB: distributed sequence generators avoid the bottleneck of a single counter by allocating ranges. The bump is digit-array addition at the byte level.

The pattern is universal: arithmetic on numbers that are too big, too precise, or too dangerous to be held in a native integer.

Variants you'll see elsewhere

  • add-two-numbers (linked-list digits): the same right-to-left carry walk, but the digits are linked-list nodes instead of array slots. Plus-one is the warm-up.
  • add-binary: same idea, base two. Carry is also at most one because both inputs are bits.
  • add-strings: arbitrary-length addition of two strings of digits. The carry rule is identical; you just sum two digits plus the carry instead of just one.
  • multiply-strings: schoolbook multiplication using digit arrays. Carry propagation at every step.

Once you have plus-one in your fingers, the rest of the digit-arithmetic family is just bookkeeping.

How parikshan turns this into a learning loop

After you read this article and click through to the practice link, the parikshan flow integrates four layers:

  1. The editor runs your code against public tests for instant feedback, and against per-session dynamic private tests (generated freshly per session) so memorising someone else's solution is useless. The dynamic tests for plus-one will include all-nines, single-digit zero, and a long array with a nine deep in the middle, three places people forget.
  2. Hints are graduated. Take the first hint and you sacrifice a few integrity points for one line of nudge ("think about how carry propagates"). Take the third hint and you get the full algorithmic skeleton, at a larger penalty. The integrity score is the platform's measure of independent thinking.
  3. The AI training assistant is a sparring partner, not an answer key. In exam mode, you can ask it to Explain the problem, Review your current code, Find Bugs, Add Comments, or Optimise. Each request docks integrity by a small amount, so the cost forces you to choose deliberately. In practice mode, AI chat is free-form and free of penalty: the place to learn the pattern at leisure.
  4. The dispute flow runs after the verdict. If you believe your solution is correct and the judge is wrong (every coder's instinct), one click sends the code to a human reviewer. The reviewer can override the verdict.

Attempt the problem in practice mode first, then redo it in exam mode with no help. When you can solve it in under three minutes including the all-nines edge case, the pattern is in your fingers.

In the AI-integrated workspace

In your future job, you will not write plus-one from scratch. An agent will. Your job is to:

  1. Recognise, when reading a payments or OCR spec, that float arithmetic is a trap and digit-array arithmetic is the correct model. That recognition is the entire skill.
  2. Tell the agent precisely: "increment the digit array in place from the right, prepend on overflow, never convert through int."
  3. Read the agent's code and verify it does not silently call int(...) then str(...). That is the failure mode you are paid to catch.
  4. Stress-test on the cases the agent will silently miss: [9], [0], all-nines of length 1000, an interior nine like [1, 9, 9, 2, 9].

Candidates who can name "this is plus-one, never use float" within seconds of reading a payments spec are the ones who direct AI agents productively. Candidates who cannot will eventually ship a float-rounding bug and explain it to the CFO.