I'm just starting out on LeetCode doing some of the 'easy' problems and I'm trying to solve a problem called 'PlusOne' where you're asked to do the following:
"You are given a large integer represented as an integer array digits, where each digits[i] is the i-th 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."
Below is the solution I came up with. The input is digits = [1, 2, 3].
static int[] PlusOne(int[] digits)
{
string digitsToString = string.Join(string.Empty, digits);
int stringToInt = Convert.ToInt32(digitsToString);
stringToInt = 1;
string outputString = stringToInt.ToString();
int[] output = outputString.Select(x => Convert.ToInt32(x)).ToArray();
/*
Tried this as well, but just got the same result
char[] outputCharArr = stringToInt.ToString().ToCharArray();
int[] output = Array.ConvertAll(outputCharArr, Convert.ToInt32);
*/
return output;
}
The expected output is [1, 2, 4], but what I get is [49, 50, 52]. I'm completely baffled as to why this the output I'm getting so if someone could explain it to me I'd be extremely appreciative!
CodePudding user response:
The problem was from here:
string outputString = stringToInt.ToString();
int[] output = outputString.Select(x => Convert.ToInt32(x)).ToArray();
Which you are converting a char
to int
.
According to here, you will get the result of 49
when casting from a '1'
(char) [Known as ASCII].
char | int |
---|---|
'1' | 49 |
'2' | 50 |
'4' | 52 |
If your int
array with a guarantee with orders (smallest to largest), you can just update the last value of the array as below:
static int[] PlusOne(int[] digits)
{
digits[digits.Length - 1] = 1;
return digits;
}
CodePudding user response:
Yong's answer will solve the problem you're having with your approach. Your solution will work up until a point but for very large numbers it will fail once you get out of range for a 32 bit integer.
Alternatively you can increment the digits like Yong hinted at, however you need to handle rolling over to "10" back to 0 and incrementing the previous digit, which is possibly one of the goals of the exercise.
public static int[] PlusOne(int[] digits)
{
return incrementPosition(digits, digits.Length-1);
}
private static int[] incrementPosition(int[] digits, int position)
{
if (position < 0 || position > digits.Length)
throw new ArgumentException("Position falls outside of digit length.");
if (digits[position] < 0 || digits[position] > 9)
throw new ArgumentException($"The digit at position {position} was out of range.");
digits[position] ;
if (digits[position] >= 10)
{
digits[position] = 0;
if (position > 0)
digits = incrementPosition(digits, position - 1);
else
{
int[] updatedDigits = new int[digits.Length 1];
updatedDigits[0] = 1;
digits.CopyTo(updatedDigits, 1);
digits = updatedDigits;
}
}
return digits;
}
This assumes that the array contains single-digit elements /w base-10 incrementing, and represents a positive value. There is a basic check for when a particular digit is incremented. This code handles when a digit rolls over, including when a "full" array (I.e. 9, 9, 9) rolls over, inserting a new digit converting 999 to 1000.