Change bits to make specific OR value

0 0 12 minutes read

Given two positive integers A and B, we can change at most K bits in both the numbers to make OR of them equal to a given target number T. In the case of multiple solutions try to keep A as small as possible. Examples :

Input : A = 175,
        B = 66,
        T = 100,
        K = 5
Output : A = 36
         B = 64
Initial bits of A = 1010 1111
Changed bits of A = 0010 0100
Initial bits of B = 0100 0010
Changed bits of B = 0100 0000
OR of changed Bits = 0110 0100
Which has decimal value equal to Target T.

Input : A = 175,
        B = 66,
        T = 100,
        K = 4
Output : Not Possible
It is not possible to get OR of
A and B as T, just by changing K bits.

We can solve this problem by iterating over all bits of A and B and greedily changing them that is,

If i-th bit of Target T is 0 then set i-th bits of A and B to 0 (if not already)
If i-th bit of Target T is 1 then we will try to set one of the bits to 1 and we will change i-th bit of B only to 1(if not already) to minimize A.

After above procedure, if changed bits are more than K, then it is not possible to get OR of A and B as T by changing at most K bits. If changed bits are less than k, then we can further minimize the value of A by using remaining value of K for which we will loop over bits one more time and if at any time,

i-th A bit is 1 and i-th B bit is 0 then we will make 2 changes and flip both.
i-th A and B bits are 1 then again we will make 1 change and flip A’s bit.

Total time complexity of above solution will be O(max number of bits).

C++

// C++ program to change least bits to
// get desired OR value
#include <bits/stdc++.h>
using namespace std;
 
// Returns max of three numbers
int max(int a, int b, int c)
{
    return max(a, max(b, c));
}
 
// Returns count of bits in N
int bitCount(int N)
{
    int cnt = 0;
    while (N)
    {
        cnt++;
        N >>= 1;
    }
    return cnt;
}
 
// Returns bit at 'pos' position
bool at_position(int num, int pos)
{
    bool bit = num & (1<<pos);
    return bit;
}
 
//    Utility method to toggle bit at
// 'pos' position
void toggle(int &num,int pos)
{
    num ^= (1 << pos);
}
 
//    method returns minimum number of bit flip
// to get T as OR value of A and B
void minChangeToReachTaregetOR(int A, int B,
                               int K, int T)
{
    int maxlen = max(bitCount(A), bitCount(B),
                                  bitCount(T));
 
    // Loop over maximum number of bits among
    // A, B and T
    for (int i = maxlen - 1; i >= 0; i--)
    {
        bool bitA = at_position(A, i);
        bool bitB = at_position(B, i);
        bool bitT = at_position(T, i);
 
        // T's bit is set, try to toggle bit
        // of B, if not already
        if (bitT)
        {
            if (!bitA && !bitB)
            {
                toggle(B, i);
                K--;
            }
        }
        else
        {
            //    if A's bit is set, flip that
            if (bitA)
            {
                toggle(A, i);
                K--;
            }
 
            //    if B's bit is set, flip that
            if (bitB)
            {
                toggle(B, i);
                K--;
            }
        }
    }
 
    //    if K is less than 0 then we can make A|B == T
    if (K < 0)
    {
        cout << "Not possible\n";
        return;
    }
 
    // Loop over bits one more time to minimise
    // A further
    for (int i = maxlen - 1; K > 0 && i >= 0; --i)
    {
        bool bitA = at_position(A, i);
        bool bitB = at_position(B, i);
        bool bitT = at_position(T, i);
 
        if (bitT)
        {
            // If both bit are set, then Unset
            // A's bit to minimise it
            if (bitA && bitB)
            {
                toggle(A, i);
                K--;
            }
        }
 
        // If A's bit is 1 and B's bit is 0,
        // toggle both
        if (bitA && !bitB && K >= 2)
        {
            toggle(A, i);
            toggle(B, i);
            K -= 2;
        }
    }
 
    //    Output changed value of A and B
    cout << A << " " << B << endl;
}
 
// Driver code
int main()
{
    int A = 175, B = 66, K = 5, T = 100;
    minChangeToReachTaregetOR(A, B, K, T);
    return 0;
}

Java

// Java program to change least bits to
// get desired OR value
 
class GFG {
     
    // Returns max of three numbers
    static int max(int a, int b, int c)
    {
        return Math.max(a, Math.max(b, c));
    }
     
    // Returns count of bits in N
    static int bitCount(int N)
    {
        int cnt = 0;
        while (N != 0)
        {
            cnt++;
            N >>= 1;
        }
        return cnt;
    }
     
    // Returns bit at 'pos' position
    static int at_position(int num, int pos)
    {
        int bit = num & (1<<pos);
        return bit;
    }
     
    //    Utility method to toggle bit at
    // 'pos' position
    static int toggle(int num,int pos)
    {
        num ^= (1 << pos);
        return num;
    }
     
    //    method returns minimum number of bit flip
    // to get T as OR value of A and B
    static void minChangeToReachTaregetOR(int A, int B,
                                   int K, int T)
    {
        int maxlen = max(bitCount(A), bitCount(B),
                                      bitCount(T));
     
        // Loop over maximum number of bits among
        // A, B and T
        for (int i = maxlen - 1; i >= 0; i--)
        {
            int bitA = at_position(A, i);
            int bitB = at_position(B, i);
            int bitT = at_position(T, i);
     
            // T's bit is set, try to toggle bit
            // of B, if not already
            if (bitT != 0)
            {
                if ((bitA == 0) && (bitB == 0))
                {
                    B = toggle(B, i);
                    K--;
                }
            }
            else
            {
                //    if A's bit is set, flip that
                if (bitA != 0)
                {
                    A = toggle(A, i);
                    K--;
                }
     
                //    if B's bit is set, flip that
                if (bitB != 0)
                {
                    B = toggle(B, i);
                    K--;
                }
            }
        }
     
        //    if K is less than 0 then we can make A|B == T
        if (K < 0)
        {
            System.out.println("Not possible");
            return;
        }
     
        // Loop over bits one more time to minimise
        // A further
        for (int i = maxlen - 1; K > 0 && i >= 0; --i)
        {
            int bitA = at_position(A, i);
            int bitB = at_position(B, i);
            int bitT = at_position(T, i);
     
            if (bitT != 0)
            {
                // If both bit are set, then Unset
                // A's bit to minimise it
                if ((bitA != 0) && (bitB != 0))
                {
                    toggle(A, i);
                    K--;
                }
            }
     
            // If A's bit is 1 and B's bit is 0,
            // toggle both
            if ((bitA != 0) && (bitB == 0) && K >= 2)
            {
                toggle(A, i);
                toggle(B, i);
                K -= 2;
            }
        }
     
        //    Output changed value of A and B
        System.out.println(A + " " + B);
    }
     
    //Driver Code
    public static void main(String[] args) {
        int A = 175, B = 66, K = 5, T = 100;
        minChangeToReachTaregetOR(A, B, K, T); 
    }
}
 
 
//This code is contributed by phasing17

Python3

# Python3 program to change least bits to
# get desired OR value
 
# Returns count of bits in N
def bitCount(N):
 
    cnt = 0;
    while (N > 0):
        cnt += 1
        N >>= 1
     
    return cnt
     
# Returns bit at 'pos' position
def at_position(num, pos):
 
    bit = num & (1<<pos)
    return (bit != 0) 
     
#    Utility method to toggle bit at
# 'pos' position
def toggle(num, pos):
 
    num ^= (1 << pos)
    return num
 
#  method returns minimum number of bit flip
# to get T as OR value of A and B
def minChangeToReachTaregetOR(A, B, K, T):
 
    maxlen = max(bitCount(A), bitCount(B), bitCount(T));
 
    # Loop over maximum number of bits among
    # A, B and T
    for i in range(maxlen - 1, -1, -1):
     
        bitA = at_position(A, i);
        bitB = at_position(B, i);
        bitT = at_position(T, i);
 
        # T's bit is set, try to toggle bit
        # of B, if not already
        if (bitT > 0):
            if ((not bitA) and (not bitB)):
             
                B = toggle(B, i)
                K -= 1
         
        else:
            #    if A's bit is set, flip that
            if (bitA > 0):
                A = toggle(A, i)
                K -= 1
 
            #    if B's bit is set, flip that
            if (bitB > 0):
             
                B = toggle(B, i)
                K -= 1
 
    #    if K is less than 0 then we can make A|B == T
    if (K < 0):
     
        print("Not possible");
        return;
     
 
    # Loop over bits one more time to minimise
    # A further
    i = maxlen - 1
    while True:
        if K < 0 or i < 0:
            break
     
        bitA = at_position(A, i);
        bitB = at_position(B, i);
        bitT = at_position(T, i);
 
        if (bitT > 0):
            # If both bit are set, then Unset
            # A's bit to minimise it
            if (bitA and bitB):
                A = toggle(A, i)
                K -= 1
 
        # If A's bit is 1 and B's bit is 0,
        # toggle both
        if ((bitA != 0) and (not bitB) and K >= 2):
 
            A = toggle(A, i)
            B = toggle(B, i)
            K -= 2
         
         
        i -= 1
     
 
    #    Output changed value of A and B
    print(A, B)
     
# Driver code
A = 175
B = 66
K = 5
T = 100
minChangeToReachTaregetOR(A, B, K, T)
 
# This code is contributed by phasing17

C#

// C# program to change least bits to
// get desired OR value
using System;
 
class GFG {
 
    // Returns max of three numbers
    static int max(int a, int b, int c)
    {
        return Math.Max(a, Math.Max(b, c));
    }
 
    // Returns count of bits in N
    static int bitCount(int N)
    {
        int cnt = 0;
        while (N != 0) {
            cnt++;
            N >>= 1;
        }
        return cnt;
    }
 
    // Returns bit at 'pos' position
    static int at_position(int num, int pos)
    {
        int bit = num & (1 << pos);
        return bit;
    }
 
    //    Utility method to toggle bit at
    // 'pos' position
    static int toggle(int num, int pos)
    {
        num ^= (1 << pos);
        return num;
    }
 
    //    method returns minimum number of bit flip
    // to get T as OR value of A and B
    static void minChangeToReachTaregetOR(int A, int B,
                                          int K, int T)
    {
        int maxlen
            = max(bitCount(A), bitCount(B), bitCount(T));
 
        // Loop over maximum number of bits among
        // A, B and T
        for (int i = maxlen - 1; i >= 0; i--) {
            int bitA = at_position(A, i);
            int bitB = at_position(B, i);
            int bitT = at_position(T, i);
 
            // T's bit is set, try to toggle bit
            // of B, if not already
            if (bitT != 0) {
                if ((bitA == 0) && (bitB == 0)) {
                    B = toggle(B, i);
                    K--;
                }
            }
            else {
                //    if A's bit is set, flip that
                if (bitA != 0) {
                    A = toggle(A, i);
                    K--;
                }
 
                //    if B's bit is set, flip that
                if (bitB != 0) {
                    B = toggle(B, i);
                    K--;
                }
            }
        }
 
        //    if K is less than 0 then we can make A|B == T
        if (K < 0) {
            Console.WriteLine("Not possible");
            return;
        }
 
        // Loop over bits one more time to minimise
        // A further
        for (int i = maxlen - 1; K > 0 && i >= 0; --i) {
            int bitA = at_position(A, i);
            int bitB = at_position(B, i);
            int bitT = at_position(T, i);
 
            if (bitT != 0) {
                // If both bit are set, then Unset
                // A's bit to minimise it
                if ((bitA != 0) && (bitB != 0)) {
                    toggle(A, i);
                    K--;
                }
            }
 
            // If A's bit is 1 and B's bit is 0,
            // toggle both
            if ((bitA != 0) && (bitB == 0) && K >= 2) {
                toggle(A, i);
                toggle(B, i);
                K -= 2;
            }
        }
 
        //    Output changed value of A and B
        Console.WriteLine(A + " " + B);
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int A = 175, B = 66, K = 5, T = 100;
        minChangeToReachTaregetOR(A, B, K, T);
    }
}
 
// This code is contributed by phasing17

PHP

<?php
// PHP program to change least 
// bits to get desired OR value
 
// Returns max of three numbers
function maxDD($a, $b, $c)
{
    return max($a, (max($b, $c)));
}
 
// Returns count of bits in N
function bitCount($N)
{
    $cnt = 0;
    while ($N)
    {
        $cnt++;
        $N >>= 1;
    }
    return $cnt;
}
 
// Returns bit at 'pos' position
function at_position($num, $pos)
{
    $bit = $num & (1 << $pos);
    return $bit;
}
 
// Utility method to toggle
// bit at 'pos' position
function toggle(&$num, $pos)
{
    $num ^= (1 << $pos);
}
 
// method returns minimum 
// number of bit flip to 
// get T as OR value of A and B
function minChangeToReachTaregetOR($A, $B,
                                   $K, $T)
{
    $maxlen = max(bitCount($A),
                  bitCount($B),
                  bitCount($T));
 
    // Loop over maximum number 
    // of bits among A, B and T
    for ( $i = $maxlen - 1; $i >= 0; $i--)
    {
        $bitA = at_position($A, $i);
        $bitB = at_position($B, $i);
        $bitT = at_position($T, $i);
 
        // T's bit is set, try to toggle
        // bit of B, if not already
        if ($bitT)
        {
            if (!$bitA && !$bitB)
            {
                toggle($B, $i);
                $K--;
            }
        }
        else
        {
            // if A's bit is set, 
            // flip that
            if ($bitA)
            {
                toggle($A, $i);
                $K--;
            }
 
            // if B's bit is set,
            // flip that
            if ($bitB)
            {
                toggle($B, $i);
                $K--;
            }
        }
    }
 
    // if K is less than 0 then
    // we can make A|B == T
    if ($K < 0)
    {
    echo "Not possible\n";
        return;
    }
 
    // Loop over bits one more 
    // time to minimise A further
    for ($i = $maxlen - 1; 
         $K > 0 && $i >= 0; --$i)
    {
        $bitA = at_position($A, $i);
        $bitB = at_position($B, $i);
        $bitT = at_position($T, $i);
 
        if ($bitT)
        {
            // If both bit are set, then 
            // Unset A's bit to minimise it
            if ($bitA && $bitB)
            {
                toggle($A, $i);
                $K--;
            }
        }
 
        // If A's bit is 1 and B's 
        // bit is 0, toggle both
        if ($bitA && !$bitB && $K >= 2)
        {
            toggle($A, $i);
            toggle($B, $i);
            $K -= 2;
        }
    }
 
    // Output changed value
    // of A and B
    echo $A , " " , $B , "\n";
}
 
// Driver Code
$A = 175;
$B = 66;
$K = 5;
$T = 100;
minChangeToReachTaregetOR($A, $B, $K, $T);
 
// This code is contributed by ajit
?>

Javascript

// JavaScript program to change least bits to
// get desired OR value
 
 
// Returns max of three numbers
function max(a, b, c)
{
    return Math.max(a, Math.max(b, c));
}
 
// Returns count of bits in N
function bitCount(N)
{
    let cnt = 0;
    while (N > 0)
    {
        cnt++;
        N >>= 1;
    }
    return cnt;
}
 
// Returns bit at 'pos' position
function at_position(num, pos)
{
    let bit = num & (1<<pos);
    return (bit != 0) ? true : false;
}
 
//    Utility method to toggle bit at
// 'pos' position
function toggle(num, pos)
{
    num ^= (1 << pos);
    return num;
}
 
//    method returns minimum number of bit flip
// to get T as OR value of A and B
function minChangeToReachTaregetOR(A, B, K, T)
{
    let maxlen = Math.max(bitCount(A), bitCount(B),
                                  bitCount(T));
 
    // Loop over maximum number of bits among
    // A, B and T
    for (let i = maxlen - 1; i >= 0; i--)
    {
        let bitA = at_position(A, i);
        let bitB = at_position(B, i);
        let bitT = at_position(T, i);
 
        // T's bit is set, try to toggle bit
        // of B, if not already
        if (bitT )
        {
            if ((!bitA) && (!bitB))
            {
                B = toggle(B, i);
                K--;
            }
        }
        else
        {
            //    if A's bit is set, flip that
            if (bitA)
            {
                A = toggle(A, i);
                K--;
            }
 
            //    if B's bit is set, flip that
            if (bitB)
            {
                B = toggle(B, i);
                K--;
            }
        }
    }
 
    //    if K is less than 0 then we can make A|B == T
    if (K < 0)
    {
        console.log("Not possible");
        return;
    }
 
    // Loop over bits one more time to minimise
    // A further
    for (let i = maxlen - 1; K > 0 && i >= 0; --i)
    {
        let bitA = at_position(A, i);
        let bitB = at_position(B, i);
        let bitT = at_position(T, i);
 
        if (bitT)
        {
            // If both bit are set, then Unset
            // A's bit to minimise it
            if (bitA && bitB)
            {
                A = toggle(A, i);
                K--;
            }
        }
 
        // If A's bit is 1 and B's bit is 0,
        // toggle both
        if (bitA && !bitB && K >= 2)
        {
            A = toggle(A, i);
            B = toggle(B, i);
            K -= 2;
        }
    }
 
    //    Output changed value of A and B
    console.log(A, B);
}
 
// Driver code
let A = 175, B = 66, K = 5, T = 100;
minChangeToReachTaregetOR(A, B, K, T);
 
 
//This code is contributed by phasing17

Output :

36 64

Time Complexity: O(log(max({A, B, T})))

Auxiliary Space: O(1)

If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!