Bài tập HackerRank: Maximizing XOR

Cho 2 vòng lặp i,j chạy từ L đến R, dùng phép toán XOR để tính hai số i và j. Tìm max của phép toán i XOR j

Tìm max của phép toán i XOR j

XOR là gì ạ? Anh giải thích rõ hơn giùm e với

Phép toán thao tác bit

Trong ngôn ngữ máy tính, các phép toán trên thao tác bit (tiếng Anh: bitwise operation) được thực hiện trên một hoặc nhiều chuỗi bit hoặc số nhị phân tại cấp độ của từng bit riêng biệt. Các phép toán này được thực hiện nhanh, ưu tiên, được hỗ trợ trực tiếp bởi vi xử lý, và được dùng để điều khiển các giá trị dùng cho so sánh và tính toán. Đối với các loại vi xử lý rẻ tiền, thường thì các phép toán trên thao tác bit nhanh hơn phép chia đáng kể, đôi khi nhanh hơn phép nhân, và đôi khi nhanh hơn ph...

Bài này mình nghĩ không cần 2 vòng for đâu. Có thể chạy trong O(logR) bằng cách xét lần lượt các bit có thể =0 hay không.

Đây là code của mình:

L=input()
R=input()


def log2(n):
    c=0
    while n:
        c+=1
        n>>=1
    return c

k=log2(R)

bit=[0]*k
for i in range(k):
    t= (R>>i)-(L>>i)
    if t:
        bit[i]=1

pow2=1
res=0
for i in range(k):
    res+=bit[i]*pow2;
    pow2<<=1
print res

Cũng trong web này, bài lonely integer làm thế nào ạ, em làm kiểu lùa bò (kiểu tạo thêm một mảng B, quét mảng A, với A[i] thì tăng B[A[i]] thêm 1 ấy ạ), mà em thấy nó không cần thiết dài dòng thế, giúp em với

. Có 1 cách hay đó là sử dụng tính chất của phép xor
a xor b = b xor a
0 xor a= a
a xor a=0

Vì thế khi xor các phần tử trong mảng thì sẽ dc số xuất hiện 1 lần.
Code tham khảo: http://ideone.com/MF1LoX

bài lonely integer làm thế nào ạ

#include <iostream>

int LonelyInteger(int a[], int iSize)
{
	int iLonely = a[0];
	int iCount = 0;
	for (int i = 0; i < iSize; i++)
	{
		for (int j = 0; j < iSize; j++)
		{
			if (a[i] == a[j])
			{
				iCount++;
			}
		}
		if (iCount == 1)
		{
			iLonely = a[i];
		}
		iCount = 0;
	}
	return iLonely;
}

int main()
{
	int iLonely;
	int iSize;
	std::cin >> iSize;
	int *a = new int[iSize];
	for (int i = 0; i < iSize; i++)
	{
		std::cin >> a[i];
	}
	iLonely = LonelyInteger(a, iSize);
	std::cout << iLonely;
	delete[]a;
	return 0;
}

đây là cách làm của mình chắc cách này cũng gà

Có nhiều cách làm bài này:

• Nếu em làm kiểu lùa bò tức là dùng count sort dpt = O(max(a_i))+ O(n)
• Nếu em đếm các số theo bạn ở trên dpt = O(n^2)
• Nếu em dùng thuật toán sắp xếp rồi đếm các giá trị dpt= O(nlogn)
• Nếu dùng xor ở trên dpt = O(n)

Vậy em nên dùng cách nào ạ

Cách xor là nhanh nhất

để em search cái xor, có vẻ hay, mà bây giờ em có nên học phân tích thuật toán không nhỉ (theo như khan thì là big theta, big O gì gì ấy), hay để học sau
Sao em xem wiki, có thấy liên quan gì tới bài lonely đâu

Cái đó em từ từ học cũng dc. Làm nhiều sẽ quen thôi.
Tất nhiên là wiki không thể viết hết ứng dụng của phép xor

Vậy chị cho em ý tưởng bài đó mà = xor được không ạ
Mà cách lùa bò với cách bạn trên kia, cái nào tốt hơn (đọc n^2 so vs max + n => em không so sánh được)

Trong đề sẽ có các thông tin đó. Từ đó em có thể chọn thuật toán thích hợp