Plus One

• [leetcode 66])[https://leetcode.com/problems/plus-one/]
• Difficulty: Easy

Description

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.

Hide Company Tags: Google

Hide Tags Array: Math

Hide Similar Problems: (M) Multiply Strings (E) Add Binary

Java Solution

public class Solution {
    public int[] plusOne(int[] digits) {
        int result[] = new int[digits.length + 1];
        result[digits.length] = 1;

        for(int i = digits.length - 1; i >= 0; i-- ){
            result[i + 1] += digits[i];
            result[i] += result[i + 1] / 10;
            result[i + 1] = result[i + 1] % 10;
        }

        if(result[0] == 0) return Arrays.copyOfRange(result, 1, result.length);
        else return result;
    }
}

C++ Solution

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        vector<int> result(n + 1,0);
        result[n] = 1;

        for(int i = n - 1; i >= 0; --i){
            result[i + 1] += digits[i];
            result[i] += result[i + 1] / 10 ;
            result[i + 1] = result[i + 1] % 10;
        }

        if(result[0] == 0) result.erase(result.begin());
        return result;
    }
};

Comment

This problem is quit easy. We should pay attention to the difference in usage of c++ and java. Same algorithm comes with different method calls.

• In C++ , We use erase or insert

iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last);

Removes from the vector either a single element (position) or a range of elements ([first,last)).

This effectively reduces the container size by the number of elements removed, which are destroyed.

Because vectors use an array as their underlying storage, erasing elements in positions other than the vector end causes the container to relocate all the elements after the segment erased to their new positions. This is generally an inefficient operation compared to the one performed for the same operation by other kinds of sequence containers (such as list or forward_list).

Return Type An iterator pointing to the new location of the element that followed the last element erased by the function call. This is the container end if the operation erased the last element in the sequence.Member type iterator is a random access iterator type that points to elements.

iterator insert (const_iterator position, const value_type& val);    
iterator insert (const_iterator position, size_type n, const value_type& val);    
template <class InputIterator>
iterator insert (const_iterator position, InputIterator first, InputIterator last);
iterator insert (const_iterator position, value_type&& val);    
iterator insert (const_iterator position, initializer_list<value_type> il);

Insert elements The vector is extended by inserting new elements before the element at the specified position, effectively increasing the container size by the number of elements inserted.

This causes an automatic reallocation of the allocated storage space if -and only if- the new vector size surpasses the current vector capacity.

Because vectors use an array as their underlying storage, inserting elements in positions other than the vector end causes the container to relocate all the elements that were after position to their new positions. This is generally an inefficient operation compared to the one performed for the same operation by other kinds of sequence containers (such as list or forward_list).

The parameters determine how many elements are inserted and to which values they are initialized:

Return Type An iterator that points to the first of the newly inserted elements. Member type iterator is a random access iterator type that points to elements. If reallocations happen, the storage is allocated using the container's allocator, which may throw exceptions on failure (for the default allocator, bad_alloc is thrown if the allocation request does not succeed).

• In Java,

static int[]    Arrays.copyOfRange(int[] original, int from, int to)

More about Arrays.

static void    arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

Copies an array from the specified source array, beginning at the specified position, to the specified position of the destination array. MORE