Réduire XOR

2429. Réduire XOR

Difficulté :Moyen

Sujets : Gourmands, manipulation de bits

Ce problème vous met au défi de trouver un entier positif, x, qui remplit deux conditions : il a le même nombre de bits définis (1 dans sa représentation binaire) qu'un entier donné, num2, et son XOR au niveau du bit avec un autre entier donné, num1, est minimisé.

Exemple 1 :

• Entrée : num1 = 3, num2 = 5
• Sortie : 3
• Explication : 3 (0011) et 5 (0101) ont tous deux deux bits définis. 3 XOR 3 = 0, qui est la valeur XOR minimale possible.

Exemple 2 :

• Entrée : num1 = 1, num2 = 12
• Sortie : 3
• Explication : 12 (1100) a deux bits définis. 3 (0011) a également deux bits définis, et 3 XOR 1 = 2.

Contraintes :

• 1 ≤ num1, num2 ≤ 10⁹

Approche de la solution :

La clé est une stratégie gourmande. Pour minimiser le résultat XOR, nous souhaitons aligner autant que possible les bits définis de x avec les bits définis de num1.

1. Compter les bits définis : Déterminez le nombre de bits définis dans num2. Appelons cela targetBits.

2. Construisez x : Initialisez x à 0. Parcourez les bits de num1, en commençant par le bit le plus significatif. Pour chaque bit défini dans num1, si nous n'avons pas encore atteint targetBits, ajoutez ce bit à x. Si nous avons déjà satisfait à l'exigence targetBits, sautez cette étape. Si nous n'avons pas atteint targetBits après avoir traité tous les bits de num1, ajoutez les bits restants à x, en commençant par le bit le moins significatif.

3. Retour x : Le x construit satisfera aux conditions.

Implémentation PHP :

<?php
function minimizeXor(int $num1, int $num2): int {
    $targetBits = countSetBits($num2);
    $x = 0;
    $bitsSet = 0;

    for ($i = 30; $i >= 0; $i--) {
        if (($num1 >> $i) & 1) { // Check if the i-th bit of num1 is set
            if ($bitsSet < $targetBits) {
                $x |= (1 << $i); // Set the i-th bit of x
                $bitsSet++;
            }
        }
    }

    // If we haven't reached targetBits, add remaining bits from LSB
    for ($i = 0; $i < 31 && $bitsSet < $targetBits; $i++) {
        if (!($x & (1 << $i))) { //check if bit is not set yet
            $x |= (1 << $i);
            $bitsSet++;
        }
    }

    return $x;
}

function countSetBits(int $n): int {
    $count = 0;
    while ($n > 0) {
        $count += $n & 1;
        $n >>= 1;
    }
    return $count;
}

// Test cases
echo minimizeXor(3, 5) . PHP_EOL; // Output: 3
echo minimizeXor(1, 12) . PHP_EOL; // Output: 3
echo minimizeXor(10, 7) . PHP_EOL; //Output: 11
?>

Complexité temporelle et spatiale :

• Complexité temporelle : O(log N), où N est la valeur maximale de num1 et num2. C'est parce que nous parcourons les bits des nombres.
• Complexité spatiale : O(1), un espace supplémentaire constant est utilisé.

Cette solution améliorée offre un moyen plus clair, plus efficace et plus robuste de résoudre le problème. Les commentaires expliquent la logique à chaque étape.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!