🚀 Day 5 & Day 6 of #100DaysOfCode

🧠 𝗣𝗿𝗼𝗯𝗹𝗲𝗺 𝗼𝗳 𝘁𝗵𝗲 𝗗𝗮𝘆:

𝘗𝘳𝘰𝘥𝘶𝘤𝘵 𝘰𝘧 𝘈𝘳𝘳𝘢𝘺 𝘌𝘹𝘤𝘦𝘱𝘵 𝘚𝘦𝘭𝘧 – 𝘎𝘪𝘷𝘦𝘯 𝘢𝘯 𝘪𝘯𝘵𝘦𝘨𝘦𝘳 𝘢𝘳𝘳𝘢𝘺 𝘯𝘶𝘮𝘴, 𝘳𝘦𝘵𝘶𝘳𝘯 𝘢𝘯 𝘢𝘳𝘳𝘢𝘺 𝘰𝘶𝘵𝘱𝘶𝘵 𝘸𝘩𝘦𝘳𝘦 𝘰𝘶𝘵𝘱𝘶𝘵[𝘪] 𝘪𝘴 𝘵𝘩𝘦 𝘱𝘳𝘰𝘥𝘶𝘤𝘵 𝘰𝘧 𝘢𝘭𝘭 𝘵𝘩𝘦 𝘦𝘭𝘦𝘮𝘦𝘯𝘵𝘴 𝘰𝘧 𝘯𝘶𝘮𝘴 𝘦𝘹𝘤𝘦𝘱𝘵 𝘯𝘶𝘮𝘴[𝘪].

𝘍𝘰𝘭𝘭𝘰𝘸-𝘶𝘱: 𝘚𝘰𝘭𝘷𝘦 𝘪𝘵 𝘪𝘯 𝘖(𝘯) 𝘵𝘪𝘮𝘦 𝘸𝘪𝘵𝘩𝘰𝘶𝘵 𝘶𝘴𝘪𝘯𝘨 𝘵𝘩𝘦 𝘥𝘪𝘷𝘪𝘴𝘪𝘰𝘯 𝘰𝘱𝘦𝘳𝘢𝘵𝘰𝘳.

(𝘕𝘰𝘵𝘦: 𝘐𝘯 𝘮𝘺 𝘦𝘹𝘱𝘭𝘰𝘳𝘢𝘵𝘪𝘰𝘯, 𝘐 𝘴𝘵𝘪𝘭𝘭 𝘶𝘴𝘦𝘥 𝘵𝘩𝘦 𝘥𝘪𝘷𝘪𝘴𝘪𝘰𝘯 𝘰𝘱𝘦𝘳𝘢𝘵𝘰𝘳 𝘸𝘩𝘪𝘭𝘦 𝘵𝘳𝘺𝘪𝘯𝘨 𝘵𝘰 𝘰𝘱𝘵𝘪𝘮𝘪𝘻𝘦 𝘱𝘳𝘰𝘥𝘶𝘤𝘵 𝘤𝘢𝘭𝘤𝘶𝘭𝘢𝘵𝘪𝘰𝘯𝘴.)

🔍 𝗖𝗵𝗮𝗶𝗻 𝗼𝗳 𝗧𝗵𝗼𝘂𝗴𝗵𝘁:

🔹 𝗡𝗮𝗶𝘃𝗲 𝗔𝗽𝗽𝗿𝗼𝗮𝗰𝗵𝗲𝘀:

1)𝙏𝙬𝙤-𝙋𝙤𝙞𝙣𝙩𝙚𝙧 𝙄𝙩𝙚𝙧𝙖𝙩𝙞𝙤𝙣:

𝘐𝘥𝘦𝘢: For each index i, use a nested loop (with pointer j) to multiply all elements except when i == j.

𝘙𝘦𝘴𝘶𝘭𝘵: This yielded an O(n²) solution because for each element, we looped through nearly all the remaining elements.

2)𝙏𝙚𝙢𝙥𝙤𝙧𝙖𝙧𝙮 𝙇𝙞𝙨𝙩 Item 𝙍𝙚𝙢𝙤𝙫𝙖𝙡:

𝘐𝘥𝘦𝘢: For every index i, remove the element at that index (storing it temporarily), compute the product of the remaining elements, save it at the corresponding index in the result list, and then reinsert the element back into the list.

𝘊𝘰𝘮𝘱𝘭𝘦𝘹𝘪𝘵𝘺: Time: O(n²) overall, since removal (O(n)) plus product calculation (O(n)) is done for each of the n elements.

Space: O(n), due to the additional temporary and result lists.

3)𝙐𝙨𝙞𝙣𝙜 𝙢𝙖𝙩𝙝.𝙥𝙧𝙤𝙙():

Idea: Similar to the previous method, but instead of manually looping to compute the product, I used Python’s math.prod() to compute the product of the list after removing the current element.

Outcome:

Time: Still O(n²) due to the removal and the product computation for each element.

Space: O(n) extra space.

Though these naive methods were straightforward, they were too slow for larger inputs.

🔹 𝗜𝗺𝗽𝗿𝗼𝘃𝗲𝗺𝗲𝗻𝘁 𝗨𝘀𝗶𝗻𝗴 𝗗𝗶𝘃𝗶𝘀𝗶𝗼𝗻:

I then explored a solution where I computed the total product of all elements and then, for each index, divided the total product by the element at that index. However, this approach required careful handling of edge cases such as:

a) All Zeros: Return the original list if every element is zero.

b) Multiple Zeros: If more than one zero exists, every product should be zero.

c) Single Zero: If exactly one zero exists, compute the product of non-zero elements and place it at the zero’s index.

d) Normal Case: For other cases, perform the division for each element.

Complexity Analysis:

• Time: O(n) overall, thanks to several linear passes (for product calculation, counting zeros, and filling the result).

• Space: O(n), due to the result list.

This solution satisfied the time requirement (O(n)) but still used division, not fully addressing the follow-up constraint.

🔹 𝗙𝘂𝗿𝘁𝗵𝗲𝗿 𝗢𝗽𝘁𝗶𝗺𝗶𝘇𝗮𝘁𝗶𝗼𝗻 𝘄𝗶𝘁𝗵 𝗗𝗶𝘃𝗶𝘀𝗶𝗼𝗻 (𝗨𝘀𝗶𝗻𝗴 𝗦𝗮𝘃𝗲𝗱 𝗣𝗿𝗼𝗱𝘂𝗰𝘁𝘀):

I followed a hint to try and optimize further by saving intermediate product results. The idea was:

𝘚𝘵𝘦𝘱 1: Calculate the product of all numbers except the first element and store it as the result for index 0.

𝘚𝘵𝘦𝘱 2: For each subsequent index i, update the product using a formula like:

new_product = int(previous_result / nums[i]) * nums[i-1]

Challenges:

a) Handling zeros became tricky and led to potential division-by-zero errors.

b) A 𝗵𝗲𝗹𝗽𝗲𝗿 𝗳𝘂𝗻𝗰𝘁𝗶𝗼𝗻 was introduced to manage these edge cases.

Complexity Analysis:

• Time: Each step and check runs in O(n) overall.

• Space: O(n), as additional lists and helper copies were used.

Although this method improved efficiency by avoiding redundant product calculations, it still used the division operator and required careful edge case handling.

📌 𝗧𝗮𝗸𝗲𝗮𝘄𝗮𝘆:

Over Days 5 and 6, I experimented with multiple approaches—from the naive O(n²) solutions to various division-based methods that reduced the time complexity to O(n) with O(n) space. Despite trying hints and refining my logic (especially with saving intermediate products), managing edge cases like zeros remained challenging.

I'm still working on a fully robust solution that meets all constraints!

#100DaysOfCode #DSA #Leetcode #Python #ProblemSolving #ProductExceptSelf #CodingChallenge #TechLearning