ฟังก์ชัน modify(arr, op, index): op=0 เพิ่ม arr[index] 1, op=1 คูณทุก元素 2 หาจำนวน operation น้อยที่สุดสร้าง target array จาก zero array วิธี: นับจำนวน bit 1 ใน binary representation (op=0) และจำนวน bit สูงสุด (op=1) รวมกัน
อัลกอริทึม
- ans = [0, 0] # [increment_ops, max_double_ops]
- สำหรับแต่ละ n ใน nums:
- double = 0
- while n > 0: ถ้า n คู่ -> n//=2, double++ ; ถ้า n คี่ -> n--, ans[0]++
- ans[1] = max(ans[1], double)
- คืน sum(ans)
ตัวอย่างโค้ด
def solve(nums):
ans = [0, 0]
for n in nums:
double = 0
while n:
if n % 2 == 0:
n //= 2
double += 1
else:
n -= 1
ans[0] += 1
ans[1] = max(ans[1], double)
return sum(ans)
nums = [1, 5, 3]
print(solve(nums)) # Output: 7
อินพุต/เอาต์พุต
Input: [1,5,3] Output: 7
อธิบาย: 3 increments + 4 doubles = 7 operations
