Giả sử chúng ta có một số n. Một số được gọi là số thập phân nhị phân nếu nó là số nguyên dương và tất cả các chữ số trong ký hiệu thập phân của nó là 0 hoặc 1. Ví dụ, 1001 (một nghìn lẻ một) là số thập phân nhị phân, trong khi 1021 thì không. Từ số n, chúng ta phải biểu diễn n như tổng của một số (không nhất thiết khác nhau) các số thập phân nhị phân. Sau đó tính số lượng nhỏ nhất các số thập phân nhị phân cần thiết cho việc đó.
Ví dụ, nếu đầu vào là n = 121, thì đầu ra sẽ là 2, vì có thể biểu diễn là 110 + 11 hoặc 111 + 10.
Các bước
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:
ans := -1 while n > 0, do: ans := maximum của ans và (n mod 10) n := n / 10 return ans
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; int solve(int n) { int ans = -1; while (n > 0) { ans = max(ans, n % 10); n /= 10; } return ans; } int main() { int n = 121; cout << solve(n) << endl; }Đầu vào
121
Đầu ra
2