Arrays - Add one to number

0 users say they have been asked this quesiton in interview.
Difficulty Level:

Problem Statement:

Given a non-negative number represented as an array of digits, add 1 to the number (increment the number represented by the digits ).
The digits are stored such that the most significant digit is at the head of the list.

Example:

If the vector has [1, 2, 3]
the returned vector should be [1, 2, 4]
as 123 + 1 = 124.

Solution:
/**
 * @input A : Integer array
 * @input n1 : Integer array's ( A ) length
 * 
 * @Output Integer array. You need to malloc memory for result array, and fill result's length in length_of_array
 */
int* plusOne(int* A, int n1, int *length_of_array) {
	// SAMPLE CODE
        /*
         * *length_of_array = n1 + 1; // length of result array
         * int *result = (int *) malloc(*length_of_array * sizeof(int));
         * // DO STUFF HERE. NOTE : length_of_array can be n1 OR n1 + 1. 
         * return result;
         */
	int len = n1;
	int i,j,carry = 1, temp;
	int *result;
	int length = 0;
	
	result = (int*)malloc((len+1) * sizeof(int));
	
	for (i = len - 1; i >= 0; i--) {
		j = A[i] + carry;
		carry = 0;
		if (j > 9) {
			carry = 1;
			j = j % 10;
		}
		
		result[length++] = j;
	}
		
	if (carry) {
		result[length++] = 1;
	}
	
	for (i = 0, j = length - 1; i <= j; i++, j--) {
		temp = result[i];
		result[i] =  result[j];
		result[j] = temp;
	}

	// remove leading zeros from result
	for (i = 0; i <  length; i++) {
		if (result[i] != 0) {
			break;
		}
	}
	*length_of_array = length - i;
	result = result + i;
	
	return result;
}

comments powered by Disqus