Рубрики

Выберите X так, чтобы (A xor X) + (B xor X) было минимизировано

Даны два целых числа А и В. Задача состоит в том, чтобы выбрать целое число X так , чтобы (A xor X) + (B xor X) было минимально возможным.

Примеры:

Input: A = 2, B = 3
Output: X = 2, Sum = 1

Input: A = 7, B = 8
Output: X = 0, Sum = 15

Простое решение состоит в том, чтобы сгенерировать всю возможную сумму, взяв xor из A и B со всеми возможными значениями X ≤ min (A, B) . Для генерации всех возможных сумм потребуется время O (N), где N = min (A, B) .

Эффективное решение основано на том факте, что число X будет содержать установленные биты только в том индексе, где и A, и B содержат установленный бит, так что после операции xor с X этот бит будет не установлен. Это займет всего O (Log N) время.

Другие случаи: если по определенному индексу одно или оба числа содержат 0 (неустановленный бит), а число X содержит 1 (установленный бит), то 0 будет установлено после xor с X в A и B, тогда сумма не может быть минимизирована ,

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <iostream>

using namespace std;

  
// Функция для возврата целого числа X так, что
// (A xor X) + (B ^ X) сведено к минимуму

int findX(int A, int B)

{

    int j = 0, x = 0;

  

    // Хотя A или B отличны от нуля

    while (A || B) {

  

        // Положение, в котором и А и В

        // установить бит

        if ((A & 1) && (B & 1)) {

  

            // Вставка установленного бита в x

            x += (1 << j);

        }

  

        // сдвигаем оба числа влево

        // пройти все биты

        A >>= 1;

        B >>= 1;

        j += 1;

    }

    return x;

}

  
// Код драйвера

int main()

{

    int A = 2, B = 3;

    int X = findX(A, B);

  

    cout << "X = " << X << ", Sum = "

         << (A ^ X) + (B ^ X);

  

    return 0;

}

Джава

// Java реализация подхода

class GFG {

  

    // Функция для возврата целого числа X так, что

    // (A xor X) + (B ^ X) сведено к минимуму

    static int findX(int A, int B)

    {

        int j = 0, x = 0;

  

        // Хотя A или B отличны от нуля

        while (A != 0 || B != 0) {

  

            // Положение, в котором и А и В

            // установить бит

            if ((A % 2 == 1) && (B % 2 == 1)) {

  

                // Вставка установленного бита в x

                x += (1 << j);

            }

  

            // сдвигаем оба числа влево

            // пройти все биты

            A >>= 1;

            B >>= 1;

            j += 1;

        }

        return x;

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        int A = 2, B = 3;

        int X = findX(A, B);

  

        System.out.println("X = " + X + ", Sum = "

                           + ((A ^ X) + (B ^ X)));

    }

}

  
// Этот код предоставлен 29AjayKumar

python3

# Python 3 реализация подхода

  
# Функция для возврата целого числа X так, чтобы
# (A xor X) + (B ^ X) сведено к минимуму

def findX(A,B):

    j = 0

    x = 0

  

    # В то время как A или B отличны от нуля

    while (A or B):

          

        # Положение, в котором и А и В

        # установить бит

        if ((A & 1) and (B & 1)):

              

            # Вставка установленного бита в х

            x += (1 << j)

  

        # Сдвиг влево обоих чисел

        # пройти все биты

        A >>= 1

        B >>= 1

        j += 1

    return x

  
# Код драйвера

if __name__ == '__main__':

    A = 2

    B = 3

    X = findX(A, B)

  

    print("X =",X,", Sum =",(A ^ X) + (B ^ X))

      
# Этот код предоставлен
# Surendra_Gangwar

C #

// C # реализация подхода

using System;

  

class GFG {

  

    // Функция для возврата целого числа X так, что

    // (A xor X) + (B ^ X) сведено к минимуму

    static int findX(int A, int B)

    {

        int j = 0, x = 0;

  

        // Хотя A или B отличны от нуля

        while (A != 0 || B != 0) {

  

            // Положение, в котором и А и В

            // установить бит

            if ((A % 2 == 1) && (B % 2 == 1)) {

  

                // Вставка установленного бита в x

                x += (1 << j);

            }

  

            // сдвигаем оба числа влево

            // пройти все биты

            A >>= 1;

            B >>= 1;

            j += 1;

        }

        return x;

    }

  

    // Код драйвера

    public static void Main(String[] args)

    {

        int A = 2, B = 3;

        int X = findX(A, B);

  

        Console.WriteLine("X = " + X + ", Sum = "

                          + ((A ^ X) + (B ^ X)));

    }

}

  
// Этот код предоставлен 29AjayKumar

PHP

<?php
// PHP реализация подхода

  
// Функция для возврата целого числа X так, что
// (A xor X) + (B ^ X) сведено к минимуму

function findX($A, $B)

{

    $j = 0;

    $x = 0;

  

    // Хотя A или B отличны от нуля

    while ($A || $B) {

  

        // Положение, в котором и А и В

        // установить бит

        if (($A & 1) && ($B & 1)) 

        {

  

            // Вставка установленного бита в x

            $x += (1 << $j);

        }

  

        // сдвигаем оба числа влево

        // пройти все биты

        $A >>= 1;

        $B >>= 1;

        $j += 1;

    }

    return $x;

}

  
// Код драйвера

    $A = 2;

    $B = 3;

    $X = findX($A, $B);

  

    echo "X = " , $X , ", Sum = ",

        ($A ^ $X) + ($B ^ $X);

  
// Этот код предоставлен ajit.
?>

Выход:

X = 2, Sum = 1

Рекомендуемые посты:

Выберите X так, чтобы (A xor X) + (B xor X) было минимизировано

0.00 (0%) 0 votes