Mô tả
Cho mảng các chữ số chứa giá trị từ 0 đến 9. Nhiệm vụ tìm tổng nhỏ nhất có thể của hai số tạo từ các chữ số của mảng. Lưu ý phải dùng tất cả chữ số của mảng cho trước.
Ví dụ
Nếu mảng đầu vào là {7, 5, 1, 3, 2, 4} thì tổng nhỏ nhất là 382, vì có thể tạo hai số 135 và 247.
Thuật toán
- Sắp xếp mảng theo thứ tự tăng dần
- Tạo hai số bằng cách lấy chữ số từ mảng đã sắp xếp luân phiên: từ chỉ số chẵn và lẻ
Ví dụ mã nguồn
#include <bits/stdc++.h> using namespace std; int getMinSum(int *arr, int n) { sort(arr, arr + n); int a = 0; int b = 0; for (int i = 0; i < n; ++i) { if (i % 2 == 0) { a = a * 10 + arr[i]; } else { b = b * 10 + arr[i]; } } return a + b; } int main() { int arr[] = {7, 5, 1, 3, 2, 4}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Minimum sum = " << getMinSum(arr, n) << endl; return 0; } Khi biên dịch và chạy chương trình trên. Nó tạo ra đầu ra sau:
Kết quả
Minimum sum = 382