Số bộ tối thiểu có số nhỏ hơn Y trong C ++

Tuyên bố vấn đề

Cho một chuỗi các chữ số liên tiếp và một số Y, nhiệm vụ là tìm số bộ nhỏ nhất sao cho mọi bộ đều tuân theo quy tắc dưới đây -

• Tập hợp phải chứa các số liên tiếp
• Không thể sử dụng chữ số nào nhiều lần.
• Số trong tập hợp không được nhiều hơn Y.

Ví dụ

Nếu str =“1234” và Y =20 thì câu trả lời là 3 như các bộ dưới đây được tạo -

{12} {3} và {4}

Thuật toán

• Chuyển đổi chuỗi thành số
• Nếu số không lớn hơn Y, thì đánh dấu f =1
• Nếu số lượng vượt quá Y, thì hãy tăng số lượng nếu f =1 và khởi tạo lại f bằng 0 và cũng khởi tạo num là s [i] - ‘0’ hoặc num là 0
• Sau khi lặp lại hoàn toàn trong chuỗi, hãy tăng số lượng nếu f là 1

Ví dụ

#include <iostream>
#include <string>
using namespace std;
int getMinSets(string str, int y) {
   int cnt = 0;
   int num = 0;
   int l = str.length();
   int f = 0;
   for (int i = 0; i < l; ++i) {
      num = num * 10 + str[i] - 48;
      if (num <= y) {
         f = 1;
         continue;
      }
      if (f) {
         ++cnt;
      }
      num = str[i] - '0';
      f = 0;
      if (num <= y) {
         f = 1;
      } else {
         num = 0;
      }
   }
   if (f) {
      ++cnt;
   }
   return cnt;
}
int main() {
   string str = "1234";
   int y = 20;
   cout << "Minimum sets = " << getMinSets(str, y) << endl;
   return 0;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Minimum sets = 3