Um eine Zahl durch 4 teilbar zu machen, muss die Mindestanzahl an Ziffern gelöscht werden

In diesem Artikel werden wir ein interessantes Rechenproblem untersuchen – „Die Mindestanzahl an Ziffern, die entfernt werden müssen, um eine Zahl durch 4 teilbar zu machen“. Diese Frage wird häufig bei Programmierwettbewerben und algorithmischen Interviews gestellt und bietet eine hervorragende Übung zur Verbesserung Ihrer Fähigkeiten zur Problemlösung.

Lassen Sie uns zunächst die Problemstellung verstehen: Wir haben eine Zahl und unsere Aufgabe besteht darin, die Mindestanzahl an Ziffern so zu entfernen, dass die verbleibende Zahl durch 4 teilbar ist.

Konzeptionelles Verständnis

Das Problem liegt im Bereich der Zahlentheorie. Eine wichtige Tatsache, die es zu verstehen gilt, ist, dass eine Zahl genau dann durch 4 teilbar ist, wenn ihre letzten beiden Ziffern durch 4 teilbar sind. Diese Tatsache ist entscheidend für die Lösung unseres Problems.

Algorithmusbeschreibung

Der Algorithmus zur Lösung dieses Problems umfasst die folgenden Schritte -

• Zahlen in Zeichenfolgen umwandeln.

• Beginnen Sie am Ende der Zeichenfolge und prüfen Sie, ob die aus den letzten beiden Zeichen bestehende Zahl durch 4 teilbar ist.

• Wenn ja, geben Sie die Anzahl der gelöschten Ziffern zurück. Wenn nicht, entfernen Sie das letzte Zeichen und erhöhen Sie die Anzahl.

• Wiederholen Sie diesen Vorgang, bis die Zahl durch 4 teilbar ist oder nur noch eine Ziffer übrig ist.

Beispiel

Dies ist eine C++-Implementierung des Algorithmus -

#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;
}

Ausgabe

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

In der Funktion minRemovals initialisieren wir den Zählerstand auf 0, wodurch die Anzahl der entfernten Bits verfolgt wird. Anschließend iterieren wir vom Ende der Zahl (String) und prüfen, ob die letzten beiden Ziffern der Zahl durch 4 teilbar sind. Wenn ja, geben wir die Anzahl zurück; andernfalls geben wir die Anzahl zurück. Wenn nicht, erhöhen wir die Anzahl und fahren mit der nächsten Iteration fort.

Die Funktion

main dient als Einstiegspunkt in unser Programm, wo wir die eingegebene Zahl definieren und die Mindestanzahl der zu entfernenden Ziffern ausgeben, sodass die Zahl durch 4 teilbar ist.

Testfallbeispiel

Nehmen wir als Beispiel die Zahl 1351. Wenn wir die letzten beiden Ziffern (51) untersuchen, sehen wir, dass sie nicht durch 4 teilbar ist. Daher entfernen wir die letzte Ziffer (1) und erhalten die Zahl 135. Wir überprüfen noch einmal und stellen fest, dass die letzten beiden Ziffern (35) immer noch nicht durch 4 teilbar sind. Daher entfernen wir die letzte Ziffer (5) und lassen die Zahl 13 übrig. Die letzten beiden Ziffern (13) sind nicht durch 4 teilbar, daher streichen wir die letzte Ziffer (3). Jetzt bleibt uns die Zahl 1, die nicht durch 4 teilbar ist, aber wir können keine weiteren Zahlen entfernen. Daher müssen mindestens 3 Ziffern entfernt werden.

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität dieses Algorithmus beträgt O(n), wobei n die Anzahl der Ziffern in der Zahl ist. Die Raumkomplexität beträgt O(1), da wir im Algorithmus keine zusätzlichen Datenstrukturen verwenden.

Fazit

In diesem Artikel befassen wir uns mit einem häufigen Rechenproblem – der Bestimmung der Mindestanzahl an Ziffern, die entfernt werden müssen, um eine Zahl durch 4 teilbar zu machen. Wir haben eine prägnante C++-Lösung entwickelt, die wichtige Erkenntnisse aus der Zahlentheorie nutzt.

Das obige ist der detaillierte Inhalt vonUm eine Zahl durch 4 teilbar zu machen, muss die Mindestanzahl an Ziffern gelöscht werden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!