✅Beats 100% -Explained with [ Video ] -C++/Java/Python/JS - Bit Manipulation - Explained in Detail
\n\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nYou are given two positive integers ( n ) and ( k ). The task is to determine t
![Screenshot 2024-07-21 094758.png](https://assets.leetcode.com/users/images/babc0e80-f7a8-4594-9c7c-e7838ed25601_1721535814.744189.png)\n\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nYou are given two positive integers ( n ) and ( k ). The task is to determine the number of changes needed to make ( n ) equal to ( k ) by turning bits that are `1` in the binary representation of ( n ) to `0`. If it is impossible to make ( n ) equal to ( k ), return `-1`.\n\n1. **Initial Check:** If ( n ) contains bits that ( k ) doesn\'t have, it is impossible to make ( n ) equal to ( k ). This can be checked using bitwise operations.\n2. **Counting Bits:** Count the number of `1` bits in ( n ) and ( k ). The difference between these counts gives the number of changes needed.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Check Validity:** Use bitwise AND to ensure that ( n ) can be turned into ( k ) by checking if ( (n & k) == k ). If not, return `-1`.\n2. **Count `1` Bits:** Count the number of `1` bits in the binary representation of ( n ) and ( k ).\n3. **Calculate Changes:** Subtract the count of `1` bits in ( k ) from the count of `1` bits in ( n ) to get the number of changes needed.\n\n# Complexity\n- **Time Complexity:** ( O(log n + log k) ) since counting the bits involves iterating over the binary representation of ( n ) and ( k ).\n- **Space Complexity:** ( O(1) ) since we use a constant amount of extra space.\n\n\n# Step By Step Explanation\n\n#### Step 1: Check Validity\n\n- Perform bitwise AND operation: `n & k`. If the result is not equal to ( k ), it means ( n ) has bits set to `1` that cannot be matched to ( k ).\n\n\n#### Step 2: Count `1` Bits in `n` and `k`\n\n- Convert ( n ) and ( k ) to their binary string representations.\n- Count the number of `1` bits in both representations.\n\n\n#### Step 3: Calculate the Result\n\n- The difference `res` represents the number of changes needed to turn ( n ) into ( k ).\n\n# Example Walkthrough\n\n#### Example 1\n- **Input:** ( n = 13 ), ( k = 4 )\n- **Binary Representations:** ( n = 1101_2 ), ( k = 0100_2 )\n- **Step 1:** `13 & 4 == 4` (Valid)\n- **Count `1` Bits:** ( n = 3 ) (`1101` has 3 ones), ( k = 1 ) (`0100` has 1 one)\n- **Changes Needed:** ( 3 - 1 = 2 )\n- **Output:** `2`\n\n#### Example 2\n- **Input:** ( n = 21 ), ( k = 21 )\n- **Binary Representations:** ( n = 10101_2 ), ( k = 10101_2 )\n- **Step 1:** `21 & 21 == 21` (Valid)\n- **Count `1` Bits:** ( n = 3 ) (`10101` has 3 ones), ( k = 3 ) (`10101` has 3 ones)\n- **Changes Needed:** ( 3 - 3 = 0 )\n- **Output:** `0`\n\n#### Example 3\n- **Input:** ( n = 14 ), ( k = 13 )\n- **Binary Representations:** ( n = 1110_2 ), ( k = 1101_2 )\n- **Step 1:** `14 & 13 != 13` (Invalid)\n- **Output:** `-1`\n\nThis explanation, along with the tables, should make it clear how the logic works and how to explain it to others.\n\n\n# Code\n```java []\nclass Solution {\n    public int minChanges(int n, int k) {\n        if ( (n & k) != k)\n            return -1;\n        \n        int res = 0;\n        \n        for (char c : Integer.toBinaryString(n).toCharArray()) {\n            res += c - \'0\';    \n        }\n        \n        for (char c : Integer.toBinaryString(k).toCharArray()) {\n            res -= c - \'0\';    \n        }\n        \n        return res;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int minChanges(int n, int k) {\n        // Step 1: Check if it\'s possible to convert n to k\n        if ((n & k) != k) {\n            return -1;\n        }\n        \n        // Step 2: Count the number of 1 bits in n and k\n        int res = 0;\n        \n        string n_bin = bitset<32>(n).to_string();\n        string k_bin = bitset<32>(k).to_string();\n        \n        for (char c : n_bin) {\n            res += c - \'0\';\n        }\n        \n        for (char c : k_bin) {\n            res -= c - \'0\';\n        }\n        \n        // Step 3: Return the number of changes needed\n        return res;\n    }\n};\n```\n```Python []\nclass Solution(object):\n    def minChanges(self, n, k):\n        # Step 1: Check if it\'s possible to convert n to k\n        if (n & k) != k:\n            return -1\n        \n        # Step 2: Count the number of 1 bits in n and k\n        res = 0\n        \n        for c in bin(n)[2:]:\n            res += int(c)\n        \n        for c in bin(k)[2:]:\n            res -= int(c)\n        \n        # Step 3: Return the number of changes needed\n        return res\n        \n```\n```JavaScript []\n/**\n * @param {number} n\n * @param {number} k\n * @return {number}\n */\nvar minChanges = function(n, k) {\n    // Step 1: Check if it\'s possible to convert n to k\n    if ((n & k) !== k) {\n        return -1;\n    }\n    \n    // Step 2: Count the number of 1 bits in n and k\n    let res = 0;\n    \n    for (let c of n.toString(2)) {\n        res += parseInt(c);\n    }\n    \n    for (let c of k.toString(2)) {\n        res -= parseInt(c);\n    }\n    \n    // Step 3: Return the number of changes needed\n    return res;\n};\n```\n![upvote.png](https://assets.leetcode.com/users/images/69489d2d-a9e5-4aa2-bcd2-bbfda698e5ed_1721535792.252091.png)\n
['Bit Manipulation', 'Python', 'C++', 'Java', 'JavaScript']