Tìm mảng bằng cách sử dụng XOR khác nhau của các phần tử theo nhóm kích thước 4 trong Java

Chúng ta được cung cấp một mảng nguyên có kích thước N (kích thước là bội số của 4) và phải thực hiện phép XOR trên mảng sao cho input[1-4] tương ứng với utility_arr[1-4] và điều kiện tính toán là: Nếu arr[1-4] = {a1, a2, a3, a4} thì q[1-4] = {a1 ⊕ a2 ⊕ a3, a1 ⊕ a2 ⊕ a4, a1 ⊕ a3 ⊕ a4, a2 ⊕ a3 ⊕ a4}.

Các kịch bản đầu vào và đầu ra

Đầu vào: int[] input = { 5, 2, 3, 4 };

Đầu ra: Kết quả sau phép XOR: 4 3 2 5

Giải thích: Cửa XOR (OR độc quyền) chỉ cho đầu ra "CAO" khi cả hai đầu vào ở mức logic "KHÁC NHAU". Đầu ra là "0" nếu hai đầu vào A và B đều ở mức logic "1" hoặc "0", biến cổng này thành "cổng lẻ nhưng không phải chẵn". Nói cách khác, khi các đầu vào có số lượng 1 lẻ, đầu ra là "1".

a1 ⊕ a2 ⊕ a3 = 5 ⊕ 2 ⊕ 3 = 4
a1 ⊕ a2 ⊕ a4 = 5 ⊕ 2 ⊕ 4 = 3
a1 ⊕ a3 ⊕ a4 = 5 ⊕ 3 ⊕ 4 = 2
a2 ⊕ a3 ⊕ a4 = 2 ⊕ 3 ⊕ 4 = 5

Đầu vào: int[] input = { 7, 6, 4, 4, 3, 8, 9, 5 };

Đầu ra: Kết quả sau các phép XOR: 5 5 7 6 2 14 15 4

Giải thích: Chỉ hoạt động với input[] có kích thước là bội số của 4, các mảng kích thước khác sẽ hiển thị 0 thay cho các số ở vị trí lẻ.

Phương pháp tiếp cận

• Theo tính chất của XOR: a ⊕ a = 0 và a ⊕ 0 = a. (a ⊕ b ⊕ c) ⊕ (b ⊕ c ⊕ d) = a ⊕ d (vì (b ⊕ c) ⊕ (b ⊕ c) = 0)
• Để tính toán, mảng được chia thành các nhóm 4 và tuân theo các tính chất của XOR để tính kết quả của từng nhóm.
• Tham khảo từ tính chất trên sử dụng (a ⊕ d) để tính b và c: (a ⊕ b ⊕ d) ⊕ (a ⊕ d) = b, (a ⊕ c ⊕ d) ⊕ (a ⊕ d) = c
• Sử dụng b và c để lấy a và d: (a ⊕ b ⊕ c) ⊕ (b) ⊕ (c) = a, (b ⊕ c ⊕ d) ⊕ (b) ⊕ (c) = d
• Quá trình lặp lại cho tất cả các nhóm 4 phần tử
• Một vòng lặp với 2 con trỏ i và j chạy đến độ dài mảng chia 4, cùng giá trị tạm (ans) và mảng utility (lưu kết quả)
• Bên trong vòng lặp thực hiện các phép XOR:
  • ans = input[i] ⊕ input[i+3]
  • Utility[i+1] (tính b) = input[i+1] ⊕ ans
  • Utility[i+2] (tính c) = input[i+2] ⊕ ans
  • Utility[i] (tính a) = input[i] ⊕ ((Utility[i+1]) ^ (Utility[i+2]))
  • Utility[i+3] (tính d) = input[i+3] ⊕ ((Utility[i+1]) ^ (Utility[i+2]))
• Cập nhật con trỏ cho nhóm 4 phần tử tiếp theo
• Cuối cùng in mảng và trả về kết quả

Ví dụ mã Java

import java.util.Arrays;
import java.util.List;

public class Tutorials {
    static int ans = 0;
    
    public static void main(String args[]) {
        int[] input = {7, 1, 2, 3};
        int[] arr = new int[input.length];
        
        for (int i = 0, j = 0; j < input.length / 4; j++) {
            ans = input[i] ^ input[i + 3];
            arr[i + 1] = input[i + 1] ^ ans;
            arr[i + 2] = input[i + 2] ^ ans;
            arr[i] = input[i] ^ ((arr[i + 1]) ^ (arr[i + 2]));
            arr[i + 3] = input[i + 3] ^ (arr[i + 1] ^ arr[i + 2]);
            i += 4;
        }
        
        System.out.println("Different XORs of elements in groups of size 4 is: ");
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

Đầu ra

Different XORs of elements in groups of size 4 is : 4 5 6 0