สมมติว่าเรามีตัวเลข n ตัวเลขเป็น "ฐานสองทศนิยม" (binary decimal) ถ้าเป็นจำนวนเต็มบวก และตัวเลขทุกหลักในการเขียนทศนิยมเป็น 0 หรือ 1 เท่านั้น เช่น 1001 (หนึ่งพันหนึ่ง) เป็น binary decimal แต่ 1021 ไม่ใช่ จากตัวเลข n เราต้องแทน n เป็นผลรวมของ binary decimal บางจำนวน (ไม่จำเป็นต้องต่างกัน) จากนั้นคำนวณจำนวน binary decimal น้อยที่สุดที่จำเป็น
เช่น ถ้าค่าที่ป้อนเข้าเป็น n = 121 ผลลัพธ์จะได้ 2 เพราะสามารถแทนได้เป็น 110 + 11 หรือ 111 + 10
ขั้นตอนการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
ans := -1 ในขณะที่ n > 0 ทำ: ans := max(ans, n mod 10) n := n / 10 คืนค่า ans
ตัวอย่างโค้ด
ดูการนำไปใช้จริงด้านล่างเพื่อความเข้าใจที่ดียิ่งขึ้น:
#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; }
ข้อมูลนำเข้า
121
ข้อมูลส่งออก
2
