Étant donné un entier positif N, la tâche consiste à trouver la paire d’entiers (X, Y) tel que le XOR au niveau du bit de X et Oui est N et X * Y est maximum où le nombre de bits dans X et Oui est inférieur ou égal à N.
Exemples:
Saisir: N = 10
Sortir: 13 7
Explication: Le cas où X = 13 et Y = 7 est le choix le plus optimal car 13 x ou 7 = 10 et 13 * 7 = 91 qui est le maximum possible.
Saisir: N = 45
Sortir: 50 31
Approcher: Le problème donné peut être résolu en utilisant les observations suivantes :
- Si la avec un peu de N est 0, puis le avec un peu des deux X et Oui doit être soit 0 ou 1. Afin de maximiser le produit, définissez des bits tels que 1.
- Si la avec un peu de N est 1, puis l’un des avec un peu de X ou Oui doit être 1 et l’autre doit être 0. Depuis N doit avoir un nombre constant de bits définis, donc la somme de X et Y doit être constante.
- Si la somme de deux nombres est constante, leur produit est maximal lorsque la différence entre les deux nombres est minimisée.
D’après les observations ci-dessus, initialisez deux entiers X et Oui comme 0. Afin de minimiser la différence entre X et Oui, X doit être égal à la MSBN et Oui doit être égal à N – MSBN où MSB représente le bit le plus significatif. Aussi, pour tous les 0 bits dans N, définissez les bits respectifs dans les deux X et Oui comme 1.
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
Table des matières
C++
|
#include en utilisant l’espace de noms std ; void maximiserProduct(int N) { int MSB = (int)log2(N); entier X = 1 << MSB ; int Y = N – (1 << MSB); pour (int i = 0; i < MSB; i++) { si (!(N & (1 << i))) { X += 1 << je; Y += 1 << je; } } cout << X << " " << Y; } int main() { entier N = 45 ; maximiserProduit(N); renvoie 0 ; } |
Complexité temporelle : O(log N)
Espace auxiliaire : AU)
Attention lecteur ! N’arrêtez pas d’apprendre maintenant. Obtenez tous les concepts importants de DSA avec le Cours auto-rythmé DSA à un prix adapté aux étudiants et devenez prêt pour l’industrie. Pour compléter votre préparation de l’apprentissage d’une langue à DS Algo et bien d’autres, veuillez vous référer Cours complet de préparation aux entretiens.
Au cas où vous souhaiteriez assister cours en direct avec des experts, veuillez vous référer Cours en direct DSA pour les professionnels en activité et Programmation compétitive en direct pour les étudiants.
