Count of Good Numbers leetcode :- 1922

Optimized Count of Good Numbers | O(log n) Solution

Optimized Count of Good Numbers | O(log n) Solution šŸš€

Introduction

Counting "Good Numbers" is an interesting problem that requires us to efficiently compute large exponentiations while following specific digit placement rules. This blog post explores an optimized approach using modular exponentiation, breaks down the logic, and provides a dry run for better understanding.

Problem Statement

Given an integer n, we need to find how many valid numbers of length n can be formed such that:

  • Digits at even indices (0-based) must be even (0, 2, 4, 6, 8) → 5 choices
  • Digits at odd indices must be prime (2, 3, 5, 7) → 4 choices

Since the result can be large, we return it modulo 10⁹ + 7.

Optimized Approach

To construct such numbers, we can observe:

  • Even-indexed positions contribute 5^(odd_count)
  • Odd-indexed positions contribute 4^(even_count)

Where:

  • even_count = n // 2 (number of even-indexed positions)
  • odd_count = n - even_count (number of odd-indexed positions)

Thus, the final answer is:

(5^(odd_count) * 4^(even_count)) % (10^9 + 7)

Efficient Computation using Binary Exponentiation

Instead of computing large powers directly, we use binary exponentiation which computes x^n in O(log n) time.

Code Implementation

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        even_count, odd_count = n // 2, n - n // 2
        even_part = self.power(4, even_count, MOD)
        odd_part = self.power(5, odd_count, MOD)
        return even_part * odd_part % MOD
    
    def power(self, x: int, n: int, MOD: int) -> int:
        if x == 0:
            return 0
        if n == 0:
            return 1
        result = self.power(x, n // 2, MOD)
        result = result * result
        if n % 2 == 1:
            return x * result % MOD
        return result % MOD

Dry Run Example

Let’s walk through an example where n = 4.

Step 1: Compute Counts

even_count = 4 // 2 = 2
odd_count = 4 - 2 = 2

Step 2: Compute Powers

odd_part = 5^2 = 25
even_part = 4^2 = 16

Step 3: Compute Result Modulo 10⁹ + 7

(25 * 16) % (10^9 + 7) = 400

Final Answer

400

Complexity Analysis

  • Binary exponentiation runs in O(log n), making the solution very efficient.
  • Overall complexity: O(log n).

Conclusion

By breaking the problem into modular exponentiation, we achieve an optimized O(log n) solution. This approach ensures efficiency even for large values of n.

LeetCode Solution Link

Check out my detailed solution on LeetCode: Optimized Count of Good Numbers | O(log n) šŸš€

Comments

Post a Comment

Popular posts from this blog

3Sum Closest: O(n²) Two-Pointer Magic šŸš€ leetcode: 16

Three Sum Closest - LeetCode Solution In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference. Problem Statement Given an integer array nums of length n and an integer target , find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution. Intuition The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique . Sorting : First, sort the array. This allows us to use the two-po...
Read more

14. Longest Common Prefix

  Finding the Longest Common Prefix in JavaScript When working with arrays of strings, a common problem is finding the longest common prefix among these strings. The longest common prefix is the initial portion of all strings in the array that is identical. This is a frequent problem on coding platforms like LeetCode, and it's essential to understand how to tackle it efficiently. In this blog post, we'll dive into the intuition, approach, and complexity of finding the longest common prefix in JavaScript. Intuition The intuition behind finding the longest common prefix is simple. By sorting the array of strings lexicographically (alphabetically), we can bring the smallest and largest strings to the beginning and end of the array. The common prefix between the first and last string in this sorted array will give us the longest common prefix for the entire array. This approach leverages the natural order of strings to simplify our task. Approach Sort the Array : First, we sort the...
Read more

860. Lemonade Change

 I recently solved the "Lemonade Change" problem on LeetCode and wanted to share my approach. This problem requires us to determine if we can provide correct change to each customer in a queue, given they may pay with $5, $10, or $20 bills, while the price of lemonade is always $5. Problem Summary: Objective: Ensure each customer receives the correct change. Constraints: You can only provide change with the bills you have received from previous customers. Approach: I used a greedy algorithm to solve this problem, focusing on always giving change in the largest denominations first to maximize the availability of smaller bills for future transactions. Code Explanation: (javascript) /**  * @param {number[]} bills  * @return {boolean}  */ var lemonadeChange = function ( bills ) {     let count5 = 0 ;     let count10 = 0 ;     for ( let i = 0 ; i < bills . length ; i ++){         if ( bills [ i ] == 5 ){ ...
Read more