จำนวนตัวเลขน้อยที่สุดที่ต้องใช้แสดงทุกจำนวนเต็มต่ำกว่า N เป็นผลรวมใน C++

ข้อกำหนดโจทย์

เรามีจำนวนเต็ม N เราต้องแสดง N เป็นผลรวมของ K จำนวนเต็ม โดยที่การบวกบางส่วนหรือทั้งหมดของจำนวนเต็มเหล่านี้เราสามารถได้ตัวเลขทั้งหมดในช่วง 1 ถึง N งานคือหาค่า K ต่ำสุด

ตัวอย่าง

ถ้า N = 8 คำตอบสุดท้าย K จะเป็น 3

ถ้าเราเอาจำนวนเต็ม 1, 2, 3, และ 4 แล้วบวกบางส่วนหรือทั้งหมดของกลุ่มเหล่านี้ เราสามารถได้ตัวเลขทั้งหมดในช่วง 1 ถึง N

e.g. 1 = 1 2 = 2 3 = 3 4 = 4 5 = 1 + 5 6 = 4 + 2 7 = 4 + 3 8 = 1 + 3 + 4

อัลกอริทึม

นับจำนวนบิตจากจำนวนเต็มที่กำหนด

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
int getMinNumbers(int n) {
  int cnt = 0;
  while (n) {
    ++cnt;
    n = n >> 1;
  }
  return cnt;
}
int main() {
  int n = 8;
  cout << "Minimum required numbers = " << getMinNumbers(n) << endl;
  return 0;
}

เมื่อคุณคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้

ผลลัพธ์

Minimum required numbers = 4