Add one to a number stored in a digit array

Question

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

Example:

Given [1,2,3] which represents 123, return [1,2,4].

Given [9,9,9] which represents 999, return [1,0,0,0].

My code is not working for the input [9,8,7,6,5,4,3,2,1,0] the output comes as just [9]

Can anyone tell me why?

public class Solution {
    /**
    * @param digits a number represented as an array of digits
    * @return the result
    */
    public int[] plusOne(int[] digits) {
        // Write your code here
        float n = 0;
        for(int i = 0; i < digits.length; i++) {
            n = n*10 + digits[i];
        }
        n++;
        String s = Float.toString(n);
        s = s.substring(0, s.indexOf("."));
        int l = s.length();
        int result[] = new int[l];
        for(int i = 0; i < l; i++) {
            result[i] = Integer.parseInt(Character.toString(s.charAt(i)));
        }
        return result;
    }
}

This is look like school exercise. You teacher expect that you will work with array directly — talex
– talex, Commented Nov 23, 2015 at 16:50
@TimB because the number can be greater than the max integer value — Sadiq Husain Khan
– Sadiq Husain Khan, Commented Nov 23, 2015 at 16:51
Are you sure you aren't supposed to do this by operating on the incoming array? i.e. just start at the end, add 1. If it overflows set to 0 and add 1 to next, etc. — Tim B
– Tim B, Commented Nov 23, 2015 at 16:51

janos · Accepted Answer · 2015-11-23 18:44:14Z

3

For the input [9,8,7,6,5,4,3,2,1,0], the value of n after this code:

float n = 0;
for(int i = 0; i < digits.length; i++) {
    n = n*10 + digits[i];
}
n++;

... is 9.8765435E9. Then, you go on and take the substring of this until the decimal point, which is 9, so the result becomes 9.

It would work better if you changed the type of n from float to long, and converted to string using Long.toString.

But this whole approach of creating n, adding 1, and then converting to String, and then converting to an array is awkward, error prone, and cannot work with larger arrays, as it becomes subject to integer overflow, unless you change the type of n to BigInteger. This solution would not pass in any tests or programming interviews.

Consider this alternative that is simpler, and will work with arbitrarily many digits (as permitted by array size) without worrying about integer overflow:

public int[] plusOne(int[] digits) {
    for (int i = digits.length - 1; i >= 0; --i) {
        digits[i]++;
        if (digits[i] < 10) {
            return digits;
        }
        digits[i] = 0;
    }
    int[] result = new int[digits.length + 1];
    System.arraycopy(digits, 0, result, 1, digits.length);
    result[0] = 1;
    return result;
}

edited Nov 23, 2015 at 18:44

answered Nov 23, 2015 at 18:14

janos

126k31 gold badges242 silver badges253 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Sadiq Husain Khan Over a year ago

Your answer is the best among all of them because you provided the reason why my code was failing. Thanks for the alternative code too

talex · Accepted Answer · 2015-11-23 17:01:46Z

1

If you want to go your strange way you need to use BigInt instead of float

But normally this problem is solved by increment last digit and go to nex one in case of overflow.

Like that:

consider last digit
increment current digit
if it is 10 make change it to 0, move one digit left and go to 2. Check special case that no digit is left. In this case prepend 0 to your array
you have required result.

edited Nov 23, 2015 at 17:01

answered Nov 23, 2015 at 16:56

talex

20.8k3 gold badges34 silver badges71 bronze badges

Comments

Tim B · Accepted Answer · 2015-11-23 17:02:08Z

1

Something like this is almost certainly what they have in mind:

int result = new int[digits.length+1]; // Result with room for 1 more digit
boolean carry = true; // Are we adding 1
for (int i=digits.length-1;i>0;i++) { // Loop from end of digits
   if (carry) {
       if (digits[i]==9) { // 9 goes to 0 and carries forwards
          result[i+1]=0;
       } else {
          result[i+1]=digits[i]+1; // Other values get incremented and carry goes
          carry=false;
       }
   } else {
      result[i+1]=digits[i];
   }
}

// If we still have a carry set the new first digit (otherwise it's already at 0.
if (carry) {
  result[0]=1;
}

answered Nov 23, 2015 at 17:02

Tim B

41.3k16 gold badges87 silver badges132 bronze badges

6 Comments

talex Over a year ago

This code always add digit. even if this isn't necessary

Tim B Over a year ago

Where? It only adds if carry is true.

talex Over a year ago

I mean resulting array always longer then input

Tim B Over a year ago

Yes it will have an extra 0 at the start. That can be avoided if needed but I'll leave that for sadiq to do if it is a requirement since I already basically wrote his exercise for him. (Note that the value is correct even with a leading zero)

talex Over a year ago

Now i will complain about spoon-feeding which is not appreciated on this site. There are people who always complain. It's me :)

|

Sameer Shrestha · Accepted Answer · 2018-11-29 22:40:15Z

0

public int[] plusOne(int[] digits) {

    int n = digits.length;

    for(int i=n-1;i>=0;i--){
        if(digits[i]!=9){
            digits[i]+=1;
            return digits;
        }
        digits[i]=0;

    }
    int [] newDigits = new int [n+1];
    newDigits[0]=1;
    return newDigits;
}

answered Nov 29, 2018 at 22:40

Sameer Shrestha

1234 bronze badges

2 Comments

dwjohnston Over a year ago

Hi - generally code only answers aren't helpful. Can you explain why this code works, and how it is better/different to other solutions?

Sameer Shrestha Over a year ago

Lets start from the last digit Case I. 1. if the last digit is not equal to 9 eg: 144 then we will take last digit and add 1 to it and return returned : 145 2. If the last digit is equal to 9 eg : 129 then we will make that 9 to 0 and loop through to digit left to it returned : 130 3. if all the digits are 9 eg :999 then lets make all 9 to 0 and create a new array with digits.lenth+1 where all default elements are 0. and put 1 to first element it will be 1000 lets me know if it is not clear

Shyam Sundar Patri · Accepted Answer · 2020-09-15 06:47:53Z

0

public ArrayList<Integer> plusOne(ArrayList<Integer> A) {
       // ArrayList<Integer> abc= new ArrayList<>();
        if(A.get(0)==0){
            A.remove(0);
        }

        if(A.get(A.size()-1)<9){
            A.add(A.size()-1, A.get(A.size()-1)+1);
            A.remove(A.size()-1);
            return A;
        }
        int end= A.size()-1;
       while(A.get(end)== 9){
           A.add(end,0);
           A.remove(end+1);
          end=end-1;
           if(A.get(end)<9) {
               A.add(end, A.get(end) + 1);
               A.remove(end +1);
           }
       }
        return A;
    }

answered Sep 15, 2020 at 6:47

Shyam Sundar Patri

13 bronze badges

Collectives™ on Stack Overflow

Add one to a number stored in a digit array

Example:

5 Answers 5

1 Comment

Comments

6 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Example:

5 Answers 5

1 Comment

Comments

6 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related