Untuk membuat nombor boleh dibahagikan dengan 4, bilangan minimum digit yang perlu dipadamkan

Dalam artikel ini, kita akan meneroka masalah pengiraan yang menarik - "Bilangan minimum digit yang perlu dikeluarkan untuk menjadikan nombor boleh dibahagi dengan 4". Soalan ini ialah soalan lazim yang ditanya dalam pertandingan pengekodan dan temu bual berasaskan algoritma, dan menyediakan amalan terbaik untuk meningkatkan kemahiran menyelesaikan masalah anda.

Mula-mula, mari kita fahami penyataan masalah: Kami mempunyai nombor dan tugas kami ialah mengeluarkan bilangan digit minimum supaya nombor yang tinggal boleh dibahagi dengan 4.

Pemahaman konseptual

Masalahnya terletak pada bidang teori nombor. Fakta penting yang perlu difahami ialah nombor boleh dibahagi dengan 4 jika dan hanya jika dua digit terakhirnya boleh dibahagi dengan 4. Fakta ini penting untuk menyelesaikan masalah kita.

Penerangan algoritma

Algoritma untuk menyelesaikan masalah ini melibatkan langkah-langkah berikut -

• Tukar nombor kepada rentetan.

• Mulakan dari hujung rentetan dan semak sama ada nombor yang terdiri daripada dua aksara terakhir boleh dibahagi dengan 4.

• Jika ya, kembalikan bilangan digit yang dipadamkan. Jika tidak, keluarkan aksara terakhir dan tambahkan kiraan.

• Ulang operasi ini sehingga nombor boleh dibahagikan dengan 4 atau hanya tinggal satu digit.

Contoh

Ini ialah pelaksanaan C++ bagi algoritma -

#include<bits/stdc++.h>
using namespace std;

int minRemovals(string num) {
   int n = num.size();
   int count = 0;
   
   for (int i = n - 1; i > 0; i--) {
      if ((num[i] - '0' + (num[i - 1] - '0') * 10) % 4 == 0) {
         return count;
      }
      count++;
   }
   
   return n - 1;
}

int main() {
   string num = "1351";
   cout << "Minimum number of digits to be removed to make the number divisible by 4 is: ";
   cout << minRemovals(num) << endl;
   
   return 0;
}

Output

Minimum number of digits to be removed to make the number divisible by 4 is: 3

Dalam fungsi minRemovals kami memulakan kiraan pembilang kepada 0, yang akan menjejaki bilangan bit yang dikeluarkan. Kami kemudian lelaran dari hujung nombor (rentetan) dan semak sama ada dua digit terakhir nombor itu boleh dibahagi dengan 4. Jika ya, kami kembalikan kiraan jika tidak, kami kembalikan kiraan itu. Jika tidak, kami menambah kiraan dan meneruskan dengan lelaran seterusnya.

Fungsi

utama berfungsi sebagai titik masuk ke program kami di mana kami mentakrifkan nombor input dan mencetak bilangan minimum digit yang akan dikeluarkan supaya nombor itu boleh dibahagikan dengan 4.

Contoh kes ujian

Mari kita ambil nombor 1351 sebagai contoh. Apabila kita meneliti dua digit terakhir (51), kita melihat bahawa ia tidak boleh dibahagikan dengan 4. Oleh itu, kami mengeluarkan digit terakhir (1) dan mendapatkan nombor 135. Kami menyemak semula dan melihat bahawa dua digit terakhir (35) masih tidak boleh dibahagikan dengan 4. Oleh itu, kami mengeluarkan digit terakhir (5), meninggalkan nombor 13. Dua digit terakhir (13) tidak boleh dibahagikan dengan 4, jadi kami memadamkan digit terakhir (3). Sekarang, kita ditinggalkan dengan nombor 1, yang tidak boleh dibahagikan dengan 4, tetapi kita tidak boleh mengeluarkan sebarang nombor lagi. Oleh itu, bilangan minimum digit yang perlu dikeluarkan ialah 3.

Kerumitan masa dan ruang

Kerumitan masa bagi algoritma ini ialah O(n), dengan n ialah bilangan digit dalam nombor itu. Kerumitan ruang ialah O(1) kerana kami tidak menggunakan sebarang struktur data tambahan dalam algoritma.

Kesimpulan

Dalam artikel ini, kami menyelidiki masalah pengkomputeran biasa - menentukan bilangan minimum digit yang perlu dikeluarkan untuk menjadikan nombor boleh dibahagi dengan 4. Kami membangunkan penyelesaian C++ ringkas menggunakan cerapan utama daripada teori nombor.

Atas ialah kandungan terperinci Untuk membuat nombor boleh dibahagikan dengan 4, bilangan minimum digit yang perlu dipadamkan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!