สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และอีกค่าหนึ่งคือ k เราต้องปฏิบัติตาม k ครั้ง:เลือกหมายเลขใดก็ได้ในรายการ ในการแทนค่าไบนารีของตัวเลขนั้น ให้เลือกบิตที่เป็น 0 และทำให้เป็น 1 สุดท้าย เราต้องคืนค่าผลรวมต่ำสุดที่เป็นไปได้ของตัวเลขทั้งหมดหลังจากดำเนินการ k หากคำตอบสูงเกินไป ให้คืนค่าโหมดผลลัพธ์ 10^9+7
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[4, 7, 3] k =2 ผลลัพธ์จะเป็น 17 เนื่องจากเลขฐานสองของ 4 คือ 100, 3 คือ 011 และ 7 คือ 111 เนื่องจากเราต้องตั้งค่า 2 บิตเราสามารถตั้งค่าบิตของ 4 ให้เป็น 111 (7) แล้วผลรวมจะเท่ากับ 7 + 7 + 3 =17
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
-
ตอบ :=0, ผม :=0
-
ในขณะที่ k ไม่ใช่ศูนย์ ให้ทำ
-
สำหรับแต่ละ n เป็น num ทำ
-
ถ้า (n / 2^i) เป็นคู่ ดังนั้น
-
ans :=ans + 2^i
-
k :=k - 1
-
ถ้า k เท่ากับ 0 แล้ว
-
ออกจากวง
-
-
-
-
ผม :=ผม + 1
-
-
return (ans + ผลรวมขององค์ประกอบทั้งหมดของ nums) mod m
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
ตัวอย่าง
class Solution: def solve(self, nums, k): m = (10 ** 9 + 7) ans = 0 i = 0 while k: for n in nums: if (n >> i) & 1 == 0: ans += 1 << i k -= 1 if k == 0: break i += 1 return (ans + sum(nums)) % m ob = Solution() nums = [4, 7, 3] k = 2 print(ob.solve(nums, k))
อินพุต
[4, 7, 3], 2
ผลลัพธ์
17
