I was doing a question on leetcode 66. Plus One https://leetcode.com/problems/plus-one/
You are given a large integer represented as 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.
Increment the large integer by one and return the resulting array of digits.
Example 1
Input: digits = [1,2,3]
Output: [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].
My solution for the given problem was:
class Solution {
public int[] plusOne(int[] digits) {
int num = 0;
for (int a : digits) {
num = 10*num a;
}
int n=num 1;
String str=String.valueOf(n);
int arr[]=new int[str.length()];
for(int i=0;i<str.length();i ){
arr[i]=str.charAt(i)-'0';
}
return arr;
}
}
In the above problem, I was getting many test cases failed one of which is :
Example:
Input:
[9,8,7,6,5,4,3,2,1,0]
Output:
[1,2,8,6,6,0,8,6,1,9]
Expected:
[9,8,7,6,5,4,3,2,1,1]
Can anyone help me with it?
CodePudding user response：
Think before you leap. And consider the edges.
Why would they do the seemingly idiotic move of storing an number, digit by digit, in an int array? Makes no sense, right?
Except... computers aren't magic. int can't represent any number. A computer's storage is infinite. Specifically, an int covers 32 bits (4 bytes), and thus can only represent at most 2^32 different numbers. int 'uses' its alloted space of 2^32 by dividing it evenly amongst positive and negative numbers, but negative numbers get one more (because the '0' is in the positive space). In other words, all numbers from -2^31 to 2^31-1, inclusive.
9876543210 is larger than that.
You're trying to turn that array of digits into an int and that is a dead end. Once you do that, you get wrong answers and there is no fixing this. your algorithm is wrong. You can figure this stuff out, and you should always do that with leetcode-style problems, by first carefully reading the assignment. The assignment covers the limits. It says how large these arrays can be, and I'm sure it says that they can be quite large; large enough that the number inside it is larger than 2^31-1. Probably larger than 2^63-1 (which a long can reach).
Then you know the algorithm you need to write can't involve 'turn it into an int first'. That's usually the point (many problems are trivial if small, but become interesting once you make things large).
The algorithm they want you to write must not involve any conversion whatsoever. Increment the array in place. This isn't hard (just think about it: without converting anything, how do you turn [1, 2, 3] into [1, 2, 4]? That should be simple. Then think about how to deal with [1, 9, 9]. Finally, think about how to deal with [9, 9, 9]. Then you've covered all the cases and you have your answer.
CodePudding user response：
This is a pretty trivial task, but in some test cases the value is too high to represent even as long, so the best candidate is BigInteger.
public int[] plusOne(int[] digits) {
BigInteger val = BigInteger.ZERO;
for (int i = 0; i < digits.length; i )
val = val.multiply(BigInteger.TEN).add(BigInteger.valueOf(digits[i]));
val = val.add(BigInteger.ONE);
String str = val.toString();
digits = str.length() == digits.length ? digits : new int[str.length()];
for (int i = 0; i < digits.length; i )
digits[i] = str.charAt(i) - '0';
return digits;
}
P.S. Sure, you can do this without BigInteger.
public int[] plusOne(int[] digits) {
boolean carry = true;
for (int i = digits.length - 1; carry && i >= 0; i--) {
carry = digits[i] == 9;
digits[i] = carry ? 0 : digits[i] 1;
}
if (carry) {
int[] tmp = new int[digits.length 1];
tmp[0] = 1;
System.arraycopy(digits, 0, tmp, 1, digits.length);
digits = tmp;
}
return digits;
}
CodePudding user response：
Think about a mileage counter in a car. How does it work? Whenever a 9 turns around, it turns the number left to it too.
So for incrementing by one, you'd start from the right, increment by one and if you incremented it to a 10, set it to a 0 instead and continue with the next digit to the left. If you reached the leftmost digit and still didnt finish, add a 1 to the left and set everything else to 0.
Example:
8
9 <- incremented rightmost
10 <- 9 turned to a 10, leftmost digit reached, add a 1 to the left and set everything else to 0
...
18
19 <- incremented rightmost
20 <- 9 turned to a 10, set to 0 instead, increment the next one to the left (1 -> 2), finished
...
108
109 <- incremented rightmost
110 <- 9 turned to a 10, set to 0 instead, increment the next one to the left (1 -> 2), finished
...
998
999 <- incremented rightmost
1000 <- 9 turned to a 10, set to 0 instead, increment the next one to the left, turned to a 10 too, set to 0 instead, ...
import java.util.stream.Collectors;
import java.util.stream.IntStream;
class Scratch {
public static void main(String[] args) {
int[] digits = new int[0];
for (int i = 0; i < 100; i ) {
digits = plusOne(digits);
System.out.println(IntStream.of(digits).mapToObj(Integer::toString).collect(Collectors.joining()));
}
}
public static int[] plusOne(int[] digits) {
boolean finished = false;
for (int i = digits.length - 1; !finished && i >= 0; i--) {
if ( digits[i] % 10 == 0) {
digits[i] = 0;
} else {
finished = true;
}
}
if (!finished) {
// not finished after exiting the loop: every digit was turned from a 9 to a 10 -> we need one digit more
// initialize a new array with a length of 1 more digit, set the leftmost (index 0) to 1 (everything else is 0 by default)
digits = new int[digits.length 1];
digits[0] = 1;
}
return digits;
}
}