पायथन में जांचें कि दिए गए गुणनफल वाला उपसरणी सरणी में मौजूद है या नहीं

मान लीजिए हमारे पास एक सरणी nums है जिसमें धनात्मक और ऋणात्मक संख्याएं हैं। हमारे पास एक मान k है। हमें जांचना है कि क्या कोई उपसरणी (subarray) है जिसका गुणनफल k के बराबर है।

उदाहरण के लिए, यदि nums = [-2, -1, 1, 3, 5, 8], k = 6 है, तो आउटपुट True होगा क्योंकि उपसरणी [-2, -1, 3] का गुणनफल 6 है।

हल करने का तरीका

1. minimum := nums[0], maximum := nums[0]
2. prod_max := nums[0]
3. सरणी को पार करें:
   • यदि nums[i] < 0, तो maximum और minimum को स्वैप करें
   • maximum := max(nums[i], maximum × nums[i])
   • minimum := min(nums[i], minimum × nums[i])
   • यदि minimum या maximum k के बराबर है, तो True लौटाएं
   • prod_max := max(prod_max, maximum)
4. False लौटाएं

यह कादाने के एल्गोरिदम का संशोधित संस्करण है जो ऋणात्मक संख्याओं को संभालता है।

उदाहरण कोड

def solve(nums, k):
    minimum = nums[0]
    maximum = nums[0]
    prod_max = nums[0]
    for i in range(1, len(nums)):
        if nums[i] < 0:
            maximum, minimum = minimum, maximum
        maximum = max(nums[i], maximum * nums[i])
        minimum = min(nums[i], minimum * nums[i])
        if minimum == k or maximum == k:
            return True
        prod_max = max(prod_max, maximum)
    return False

nums = [-2, -1, 1, 3, 5, 8]
k = 6
print(solve(nums, k))

इनपुट

[-2, -1, 1, 3, 5, 8], 6

आउटपुट

True