Tìm phần tử riêng biệt trong mảng (3n+1) phần tử dùng bit operators

#1

Đề bài

image
image1223×532 33.2 KB

Cho em xin ý tưởng bài này ạ, yêu cầu đề bài là dùng các toán tử xử lý bit ( &&, ||, !, ^, >>, << ) hay các phép toán trên bit ạ.
Bài tương tự với N=2n+1 thì em đã làm được bằng cách dùng toán tử xor, rồi bám theo tính chẵn lẻ. Nhưng còn với N=3n+1 thì em chưa có hướng đi nào ạ.

#2
  1. tính a ^ b ^ c = x
  2. lấy (x xor a | x xor b | xor c)
    nếu a = b = c, kết quả trên là 0
    nếu không bằng 0 -> bị thừa ra là x

vd: a = b = c = 1
x = a ^ b ^ c = 1
x ^ a = 0
x ^ b = 0
x ^ c = 0

a = b = 1, c = 4
x = a ^ b ^ c = 4
x ^ a = 5
x ^ b = 5
x ^ c = 0

while i < len(arr) - 1:
 a, b, c = arr[i: i+3]
 x = a ^ b ^ c
 if (x ^ a | x ^ b | x ^ c) return x
 i += 3
return arr[-1]
#3

Test 4 2 4 2 1 2 4 bạn bị sai.

#4

tưởng liền nhau chứ vậy để nghĩ thêm

#5

Bài này chỉ dùng toán tử bit chứ không cho phép dùng thêm gì khác à?

#6

có dùng là được ạ, nhưng bài này thuộc phần lập trình cơ bản ạ

#7

Từ dạng bài dùng bit operator tìm phần tử riêng biệt trong mảng 2n+1 phần tử, nâng lên thành 3n+1 phần tử thì nó lại thuộc vào 1 level khác rồi :neutral_face: Nó ở tầm Google interview cơ :neutral_face: Mình không có idea gì đâu :neutral_face:

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?