การลบหลักน้อยที่สุดในตัวเลขเพื่อให้หารด้วย 10 ยกกำลัง K ลงตัวใน C++

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

กำหนดจำนวนเต็มบวกสองจำนวน N และ K หาจำนวนหลักน้อยที่สุดที่สามารถลบออกจากตัวเลข N ได้ โดยที่หลังจากการลบ ตัวเลขจะหารด้วย 10^K ลงตัว พิมพ์ -1 หากเป็นไปไม่ได้

ตัวอย่าง

ถ้า N = 10203027 และ K = 2 แล้วเราต้องลบ 3 หลัก ถ้าเราลบ 3, 2 และ 7 ตัวเลขจะกลายเป็น 10200 ซึ่งหารด้วย 10^2 ลงตัว

อัลกอริทึม

1. เริ่มตรวจสอบตัวเลขจากท้าย หากหลักปัจจุบันไม่ใช่ศูนย์ เพิ่มตัวนับ มิฉะนั้นลดตัวแปร K
2. ถ้า K เป็นศูนย์ คืนค่าตัวนับเป็นคำตอบ
3. หลังจากตรวจสอบตัวเลขทั้งหมด ตรวจสอบว่าค่า K ปัจจุบันเป็นศูนย์หรือไม่ ถ้าเป็นศูนย์ คืนค่าตัวนับ มิฉะนั้นคืนคำตอบเป็นจำนวนหลักใน N - 1
4. ถ้าตัวเลขที่กำหนดไม่มีศูนย์เลย คืนค่า -1 เป็นคำตอบ

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

#include <bits/stdc++.h>
using namespace std;
int getBitsToBeRemoved(int n, int k) {
  string s = to_string(n);
  int result = 0;
  int zeroFound = 0;
  for (int i = s.size() - 1; i >= 0; --i) {
    if (k == 0) {
      return result;
    }
    if (s[i] == '0') {
      zeroFound = 1;
      --k;
    } else {
      ++result;
    }
  }
  if (!k) {
    return result;
  } else if (zeroFound) {
    return s.size() - 1;
  }
  return -1;
}
int main() {
  int n = 10203027;
  int k = 2;
  cout << "Minimum required removals = " << getBitsToBeRemoved(n, k) << endl;
  return 0;
}

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

ผลลัพธ์

Minimum required removals = 3