Cho mảng chứa các chữ số của số không âm (chữ số quan trọng nhất ở đầu). Cộng 1 vào số đó.
- Duyệt mảng từ cuối, cộng 1 vào chữ số cuối.
- Nếu chữ số cuối là 9, đặt thành 0, nhớ = 1.
- Lặp: nếu có nhớ và cộng thành 10, làm như bước 2.
- Sau khi cộng nhớ, đặt nhớ = 0 cho vòng sau.
- Nếu mảng mở rộng do nhớ, chèn 1 vào đầu.
Ví dụ mảng [7,6,3,4] đại diện 7634, cộng 1 thành [7,6,3,5].
Ví dụ
Input: [7, 6, 9, 9] Output: [7, 7, 0, 0] Input: [4, 1, 7, 8, 9] Output: [4, 1, 7, 9, 0]
Giải thích Cộng 1 vào phần tử cuối, nếu < 9 thì xong. Nếu = 9, đặt 0 và đệ quy cho phần tử trước.
Ví dụ
#include <iostream>
using namespace std;
void sum(int arr[], int n) {
int i = n;
if(arr[i] < 9) {
arr[i] = arr[i] + 1;
return;
}
arr[i] = 0;
i--;
sum(arr, i);
if(arr[0] > 0) {
cout << arr[0] << ", ";
}
for(int i = 1; i <= n; i++) {
cout << arr[i];
if(i < n) {
cout << ", ";
}
}
}
int main() {
int n = 4;
int arr[] = {4, 1, 7, 8, 9};
sum(arr, n);
return 0;
}