Question: Given a number (integer) stored in an array of digits int[] digits Plus one and return the new array.
Source: http://oj.leetcode.com/problems/plus-one/
The number is written from left to right, so for instance, number 1234 is represented as [‘1’, ‘2’, ‘3’, ‘4’]
Plus one, the rightmost digit may overflow if it is ‘9’, so what we have to do is to add the carry from right to left if there is any. Be careful with the situation that you have to add an extra element to the leftmost digit if it overflows, for example, [‘9’, ‘9’] should return [‘1‘, ‘0’, ‘0’].
The C++ answer is given below, using the std::vector type.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution { public: vector plusOne(vector &digits) { // Note: The Solution object is instantiated only once and is reused by each test case. int len = digits.size(); digits[len - 1] ++; int k = 0; for (int i = len - 1; i >= 0; i --) { digits[i] += k; k = digits[i] / 10; digits[i] %= 10; if (k == 0) break; // no carry any more } if (k > 0) { // add extra element digits.insert(digits.begin(), 1);// push to the front } return digits; } }; |
class Solution {
public:
vector plusOne(vector &digits) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int len = digits.size();
digits[len - 1] ++;
int k = 0;
for (int i = len - 1; i >= 0; i --) {
digits[i] += k;
k = digits[i] / 10;
digits[i] %= 10;
if (k == 0) break; // no carry any more
}
if (k > 0) { // add extra element
digits.insert(digits.begin(), 1);// push to the front
}
return digits;
}
};–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
260 wordsloading...
Last Post: Coding Exercise - String to Integer (atoi) - C++ - Online Judge
Next Post: Coding Exercise – Palindrome Number - C++ - Online Judge
