Bài tập HackerRank: Maximizing XOR

hungnm03061996 · April 1, 2015, 1:31pm

Em thực sự không hiểu đề! Ai có thể giải thích đề cho em không? Em xin cảm ơn.

Rok_Hoang · February 27, 2015, 3:49am

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

hungnm03061996 · February 27, 2015, 3:52am

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

Rok_Hoang · February 27, 2015, 3:53am

Gio · February 27, 2015, 6:38am

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

nhatlonggunz · February 27, 2015, 2:47pm

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

Gio · February 27, 2015, 3:14pm

. 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

hungnm03061996 · February 28, 2015, 12:40am

#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à

Gio · February 28, 2015, 5:08am

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)

nhatlonggunz · February 28, 2015, 5:11am

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

Gio · February 28, 2015, 5:13am

Cách xor là nhanh nhất

nhatlonggunz · February 28, 2015, 5:18am

để 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

Gio · February 28, 2015, 5:21am

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

nhatlonggunz · February 28, 2015, 5:23am

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)

Gio · February 28, 2015, 5:33am

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