DAY 12 Tackling Math-Based Challenges

Hello Everyone!

I’m Somuya Khandelwal, here with updates from Day 2 of Week 3 in my competitive programming journey. Today, I focused on Math-based problems, which tested my logical reasoning and efficiency in solving number-related challenges. These problems required me to think creatively while maintaining precision, which made for a very productive and rewarding day.

---

What I Worked On Today

1. Palindrome Number (Easy Difficulty)

   • Task: Check if a given integer reads the same backward as forward.
   • Approach:
     • Initially, I converted the integer into a string and compared it with its reverse.
     • To optimize, I worked with the number directly, reversing only half of it using modulo and division and comparing it with the other half.
   • What I Learned:
     • String manipulation is convenient but not always efficient, especially for problems like this where mathematical operations save both time and space.
     • Negative numbers and numbers ending with zero need special attention as they can’t be palindromes (except for 0).

2. Plus One (Easy Difficulty)

   • Task: Increment a number represented as an array of digits by one.
   • Approach:
     • Started from the last digit, handling carry propagation by iterating backward.
     • Created a new array if the carry extended beyond the most significant digit (e.g., [9, 9] becomes [1, 0, 0]).
   • What I Learned:
     • Carry propagation can get tricky, especially when dealing with edge cases like all nines.
     • It’s important to write solutions that work for both small inputs and large arrays efficiently.

3. Factorial Trailing Zeros (Medium Difficulty)

   • Task: Find the number of trailing zeros in the factorial of a given number n.
   • Approach:
     • Instead of computing the factorial, I counted the number of factors of 5 in the numbers from 1 to n. Each factor of 5 combines with a factor of 2 to create a trailing zero.
     • Kept dividing n by 5 iteratively to count how many multiples of 5, 25, 125, etc., existed.
   • What I Learned:
     • Problems involving factorials can often be solved more efficiently by understanding patterns in prime factors rather than calculating the factorial itself.
     • Efficient algorithms are crucial to avoid unnecessary computations when working with large inputs.

---

Key Takeaways from Today

1. Optimize by Thinking Mathematically:

   • Problems like Factorial Trailing Zeros highlighted how mathematical insights can lead to efficient solutions without brute force.

2. Edge Case Awareness:

   • Tasks like Palindrome Number and Plus One reminded me of the importance of handling edge cases, whether it’s negative numbers, numbers ending in zero, or arrays with all nines.

3. Efficient Use of Resources:

   • Avoiding unnecessary conversions (e.g., converting numbers to strings) and focusing on space-efficient solutions can make a significant difference.

4. Step-by-Step Problem Solving:

   • Breaking down a problem into smaller, logical steps not only simplifies debugging but also helps in identifying potential optimizations.

---

Reflections and Challenges

The Factorial Trailing Zeros problem was the most thought-provoking today. It required a shift from direct computation to understanding the role of factors in trailing zeros. Debugging Plus One was also a great exercise in managing carry propagation—one small mistake can lead to incorrect results. Overall, these challenges reinforced my understanding of number manipulation and efficiency.

---

Looking Ahead

Tomorrow, I’ll continue with more Math-based problems, including Sqrt(x), Pow(x, n), and Max Points on a Line, which will introduce geometry and advanced computations. I’m excited to dive into these problems and see what I can learn.

Thank you for following along on my journey! Stay tuned for more updates as I continue to explore new challenges in competitive programming.

Best regards,

Somuya