2429. Minimize XOR
Difficulty: Medium
Topics: Greedy, Bit Manipulation
This problem challenges you to find a positive integer, x, that meets two conditions: it has the same number of set bits (1s in its binary representation) as a given integer, num2, and its bitwise XOR with another given integer, num1, is minimized.
Example 1:
-
Input:
num1= 3,num2= 5 - Output: 3
- Explanation: 3 (0011) and 5 (0101) both have two set bits. 3 XOR 3 = 0, which is the minimum possible XOR value.
Example 2:
-
Input:
num1= 1,num2= 12 - Output: 3
- Explanation: 12 (1100) has two set bits. 3 (0011) also has two set bits, and 3 XOR 1 = 2.
Constraints:
- 1 ≤
num1,num2≤ 109
Solution Approach:
The key is a greedy strategy. To minimize the XOR result, we want to align the set bits of x with the set bits of num1 as much as possible.
-
Count Set Bits: Determine the number of set bits in
num2. Let's call thistargetBits. -
Construct x: Initialize x to 0. Iterate through the bits of
num1, starting from the most significant bit. For each set bit innum1, if we haven't reachedtargetBitsyet, add that bit to x. If we've already met thetargetBitsrequirement, skip the bit. If we haven't reachedtargetBitsafter processing all bits ofnum1, add the remaining bits to x, starting from the least significant bit. -
Return x: The constructed x will satisfy the conditions.
PHP Implementation:
<?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
?>
Time and Space Complexity:
-
Time Complexity: O(log N), where N is the maximum value of
num1andnum2. This is because we iterate through the bits of the numbers. - Space Complexity: O(1), constant extra space is used.
This improved solution provides a clearer, more efficient, and more robust way to solve the problem. The comments explain the logic at each step.
The above is the detailed content of Minimize XOR. For more information, please follow other related articles on the PHP Chinese website!
Hot AI Tools
Undress AI Tool
Undress images for free
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Clothoff.io
AI clothes remover
Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
How do I implement authentication and authorization in PHP?
Jun 20, 2025 am 01:03 AM
TosecurelyhandleauthenticationandauthorizationinPHP,followthesesteps:1.Alwayshashpasswordswithpassword_hash()andverifyusingpassword_verify(),usepreparedstatementstopreventSQLinjection,andstoreuserdatain$_SESSIONafterlogin.2.Implementrole-basedaccessc
How can you handle file uploads securely in PHP?
Jun 19, 2025 am 01:05 AM
To safely handle file uploads in PHP, the core is to verify file types, rename files, and restrict permissions. 1. Use finfo_file() to check the real MIME type, and only specific types such as image/jpeg are allowed; 2. Use uniqid() to generate random file names and store them in non-Web root directory; 3. Limit file size through php.ini and HTML forms, and set directory permissions to 0755; 4. Use ClamAV to scan malware to enhance security. These steps effectively prevent security vulnerabilities and ensure that the file upload process is safe and reliable.
What are the differences between == (loose comparison) and === (strict comparison) in PHP?
Jun 19, 2025 am 01:07 AM
In PHP, the main difference between == and == is the strictness of type checking. ==Type conversion will be performed before comparison, for example, 5=="5" returns true, and ===Request that the value and type are the same before true will be returned, for example, 5==="5" returns false. In usage scenarios, === is more secure and should be used first, and == is only used when type conversion is required.
How do I perform arithmetic operations in PHP ( , -, *, /, %)?
Jun 19, 2025 pm 05:13 PM
The methods of using basic mathematical operations in PHP are as follows: 1. Addition signs support integers and floating-point numbers, and can also be used for variables. String numbers will be automatically converted but not recommended to dependencies; 2. Subtraction signs use - signs, variables are the same, and type conversion is also applicable; 3. Multiplication signs use * signs, which are suitable for numbers and similar strings; 4. Division uses / signs, which need to avoid dividing by zero, and note that the result may be floating-point numbers; 5. Taking the modulus signs can be used to judge odd and even numbers, and when processing negative numbers, the remainder signs are consistent with the dividend. The key to using these operators correctly is to ensure that the data types are clear and the boundary situation is handled well.
How do I stay up-to-date with the latest PHP developments and best practices?
Jun 23, 2025 am 12:56 AM
TostaycurrentwithPHPdevelopmentsandbestpractices,followkeynewssourceslikePHP.netandPHPWeekly,engagewithcommunitiesonforumsandconferences,keeptoolingupdatedandgraduallyadoptnewfeatures,andreadorcontributetoopensourceprojects.First,followreliablesource
How can you interact with NoSQL databases (e.g., MongoDB, Redis) from PHP?
Jun 19, 2025 am 01:07 AM
Yes, PHP can interact with NoSQL databases like MongoDB and Redis through specific extensions or libraries. First, use the MongoDBPHP driver (installed through PECL or Composer) to create client instances and operate databases and collections, supporting insertion, query, aggregation and other operations; second, use the Predis library or phpredis extension to connect to Redis, perform key-value settings and acquisitions, and recommend phpredis for high-performance scenarios, while Predis is convenient for rapid deployment; both are suitable for production environments and are well-documented.
What is PHP, and why is it used for web development?
Jun 23, 2025 am 12:55 AM
PHPbecamepopularforwebdevelopmentduetoitseaseoflearning,seamlessintegrationwithHTML,widespreadhostingsupport,andalargeecosystemincludingframeworkslikeLaravelandCMSplatformslikeWordPress.Itexcelsinhandlingformsubmissions,managingusersessions,interacti
How to set PHP time zone?
Jun 25, 2025 am 01:00 AM
TosettherighttimezoneinPHP,usedate_default_timezone_set()functionatthestartofyourscriptwithavalididentifiersuchas'America/New_York'.1.Usedate_default_timezone_set()beforeanydate/timefunctions.2.Alternatively,configurethephp.inifilebysettingdate.timez
