Рубрики

Найти число, которое дает минимальную сумму, когда XOR с каждым номером массива целых чисел

Для заданного массива arr [] неотрицательных целых чисел задача состоит в том, чтобы найти целое число X такое, что (arr [0] XOR X) + (arr [1] XOR X) +… + arr [n — 1] XOR X минимально возможно.

Примеры:

Input: arr[] = {3, 9, 6, 2, 4}
Output: X = 2, Sum = 22

Input: arr[] = {6, 56, 78, 34}
Output: X = 2, Sum = 170

Подход: мы проверим «i» -й бит каждого номера массива в двоичном представлении и посчитаем те числа, которые содержат «i» -й бит, установленный в «1», потому что эти установленные биты будут способствовать максимизации суммы, а не минимизации. Таким образом, мы должны установить этот бит «i» в «0», если число больше N / 2, а если число меньше N / 2, то числа с установленным битом «i» меньше и поэтому не будут повлиять на ответ. Что касается операции XOR для двух битов, мы знаем, что когда A XOR B и A и B одинаковы, то это дает результат как '0', поэтому мы сделаем этот 'i' -й бит в нашем числе (num) равным '1 ' , так что (1 XOR 1) даст ' 0 ' и минимизирует сумму.

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

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>
#include <cmath>

using namespace std;

  
// Функция для поиска целого числа X такого, что
// сумма всех элементов массива после
// XORed с X минимален

void findX(int arr[], int n)

{

    // Находим максимальный элемент массива

    int* itr = max_element(arr, arr + n);

  

    // Находим максимальное требуемое количество бит

    // в двоичном представлении

    // максимального количества

    // так вычисляется log2

    int p = log2(*itr) + 1;

  

    // Запуск цикла из p раз, который

    // количество битов, необходимых для представления

    // все элементы массива

    int X = 0;

    for (int i = 0; i < p; i++) {

        int count = 0;

        for (int j = 0; j < n; j++) {

  

            // Если биты в одной позиции установлены

            // затем посчитаем

            if (arr[j] & (1 << i)) {

                count++;

            }

        }

  

        // Если число становится больше половины

        // размер массива, то нам нужно сделать

        // этот бит '0', установив бит X в '1'

        if (count > (n / 2)) {

  

            // Снова используем операцию сдвига для вычисления

            // требуемый номер

            X += 1 << i;

        }

    }

  

    // Вычисляем минимизированную сумму

    long long int sum = 0;

    for (int i = 0; i < n; i++)

        sum += (X ^ arr[i]);

  

    // Распечатать решение

    cout << "X = " << X << ", Sum = " << sum;

}

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

int main()

{

    int arr[] = { 2, 3, 4, 5, 6 };

    int n = sizeof(arr) / sizeof(arr[0]);

  

    findX(arr, n);

  

    return 0;

}

Джава

// Java реализация вышеупомянутого подхода

import java.lang.Math;

import java.util.*;

  

class GFG

{

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

    // сумма всех элементов массива после

    // XORed с X минимален

    public static void findX(int[] a, int n)

    {

          

        // Находим максимальный элемент массива

        Collections.sort(Arrays.asList(a), null);

        int itr = a[n-1];

          

        // Находим максимальное требуемое количество бит

        // в двоичном представлении

        // максимального количества

        // так вычисляется log2

        int p = (int)(Math.log(itr)/Math.log(2)) + 1;

  

        // Запуск цикла из p раз, который

        // количество битов, необходимых для представления

        // все элементы массива

        int x = 0;

        for (int i = 0; i < p; i++)

        {

            int count = 0;

            for (int j = 0; j < n; j++)

            {

                  

                // Если биты в одной позиции установлены

                // затем посчитаем

                if ((a[j] & (1 << i)) != 0)

                    count++;

            }

  

            // Если число становится больше половины

            // размер массива, то нам нужно сделать

            // этот бит '0', установив бит X в '1'

            if (count > (n / 2))

            {

                  

                // Снова используем операцию сдвига для вычисления

                // требуемый номер

                x += 1 << i;

            }

        }

  

        // Вычисляем минимизированную сумму

        long sum = 0;

        for (int i = 0; i < n; i++)

            sum += (x ^ a[i]);

          

        // Распечатать решение

        System.out.println("X = " + x + ", Sum = " + sum);

    }

  

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

    public static void main(String[] args)

    {

        int[] a = {2, 3, 4, 5, 6};

        int n = a.length;

  

        findX(a, n);

    }

  
}

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

python3

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

from math import log2

  
# Функция, чтобы найти целое число X такое, что
# сумма всех элементов массива после
# получение XORed с X минимально

def findX(arr, n):

      

    # Нахождение максимального элемента массива

    itr = arr[0]

    for i in range(len(arr)):

          

        # Найти максимальное количество требуемых бит

        # в двоичном представлении

        № максимального числа

        # так лог2 рассчитывается

        if(arr[i] > itr):

            itr = arr[i]

  

    p = int(log2(itr)) + 1

  

    # Запуск цикла от p раз, который

    # количество битов, необходимых для представления

    # все элементы массива

    X = 0

    for i in range(p):

        count = 0

        for j in range(n):

              

            # Если биты в той же позиции установлены

            # затем увеличить счет

            if (arr[j] & (1 << i)):

                count += 1

  

        # Если счет становится больше половины

        # размер массива, то нам нужно сделать

        # этот бит '0', установив бит X в '1'

        if (count > int(n / 2)):

              

            # Снова используя операцию сдвига для расчета

            # необходимое количество

            X += 1 << i

  

    # Рассчитать минимизированную сумму

    sum = 0

    for i in range(n):

        sum += (X ^ arr[i])

  

    # Решение для печати

    print("X =", X, ", Sum =", sum)

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

if __name__=='__main__':

    arr = [2, 3, 4, 5, 6]

    n = len(arr)

    findX(arr, n)

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

C #

// C # реализация вышеуказанного подхода

using System;

using System.Linq;

  

class GFG 

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

    // сумма всех элементов массива после

    // XORed с X минимален

    public static void findX(int[] a, int n) 

    

          

        // Находим максимальный элемент массива

        int itr = a.Max(); 

          

        // Находим максимальное требуемое количество бит

        // в двоичном представлении

        // максимального количества

        // так вычисляется log2

        int p = (int) Math.Log(itr, 2) + 1; 

  

        // Запуск цикла из p раз, который

        // количество битов, необходимых для представления

        // все элементы массива

        int x = 0; 

        for (int i = 0; i < p; i++) 

        

            int count = 0; 

            for (int j = 0; j < n; j++) 

            

                  

                // Если биты в одной позиции установлены

                // затем посчитаем

                if ((a[j] & (1 << i)) != 0) 

                    count++; 

            

  

            // Если число становится больше половины

            // размер массива, то нам нужно сделать

            // этот бит '0', установив бит X в '1'

            if (count > (n / 2)) 

            

                  

                // Снова используем операцию сдвига для вычисления

                // требуемый номер

                x += 1 << i; 

            

        

  

        // Вычисляем минимизированную сумму

        long sum = 0; 

        for (int i = 0; i < n; i++) 

            sum += (x ^ a[i]); 

          

        // Распечатать решение

        Console.Write("X = " + x + ", Sum = " + sum); 

    

  

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

    public static void Main(String[] args) 

    

        int[] a = {2, 3, 4, 5, 6}; 

        int n = a.Length; 

  

        findX(a, n); 

    

  

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

Выход:

X = 6, Sum = 14

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

Найти число, которое дает минимальную сумму, когда XOR с каждым номером массива целых чисел

0.00 (0%) 0 votes