FNUM

Tác giả:

Dạng bài

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Misaki có một số \(N\), cô ấy đố bạn tìm ra được \(FNUM\) của số đó. Một \(FNUM\) được xác định là tổng các chữ số của số đó, sau đó lại tính tổng các chữ số của số mới tạo được cho đến khi chỉ còn 1 chữ số duy nhất. Bạn hãy tìm ra số cuối cùng đó nhé!

Input

Dòng đầu tiên và duy nhất chứa 1 số nguyên \(N\) \((1 \leq N \leq 10^{1000000})\)

Output

In ra 1 số nguyên là \(FNUM\) của \(N\).

Example

Test 1

Input

Output

Note

Các số được tạo ra lần lượt là \(29 \rightarrow 11 \rightarrow 2\)

Bình luận

Bài này em có cách giải hơi ngu, nếu thấy sai mong các anh chỉ bảo.

Cách thứ nhất: Dùng đệ quy, cộng hết các chữ số lại, nếu tổng lớn hơn 9 thì chạy lại lần nữa

Code:

int findNum(string input)
{
    int answer{};
    for (int i = 0; i < input.size(); i++) answer += int(input[i]) - 48;
    return (answer <= 9) ? answer : findNum(to_string(answer));
}

int main()
{
    string input;
    cin >> input;
    cout << findNum(input);
}

Cách thứ hai: Chỉ cần tính tổng hết cả dãy rồi sau đó lấy số dư của số đó chia cho 9, trường hợp chia hết xuất ra 9.

Code:

int main()
{
    string input;
    cin >> input;

    int sum {0};

    for (int i = 0; i < input.size(); i++)
    {
        sum += int(input[i]) - 48;
    }
    if (sum % 9 == 0)
        cout << '9';
    else
        cout << sum % 9;
}

4 bình luận nữa