Ugly Number III Solution In C++/Python/Java/JS
Ugly Number III Problem Description:
An ugly number is a positive integer that is divisible by a, b, or c.
Given four integers n, a, b, and c, return the nth ugly number.
Examples:
Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.
Input: n = 4, a = 2, b = 3, c = 4
Output: 6
Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4th is 6.
Input: n = 5, a = 2, b = 11, c = 13
Output: 10
Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.
Constraints:
1 ≤ n, a, b, c ≤ 10⁹
1 ≤ a * b * c ≤ 10¹⁸
It is guaranteed that the result will be in range [1, 2 × 10⁹].
Brute Force Approach
We are given three numbers a, b, and c, and need to find the nth ugly number. An ugly number is any number that is divisible by a, b, or c.
Our goal is to generate ugly numbers in increasing order and return the nth one.
What is the Smallest Possible Ugly Number?
The smallest ugly number must be min(a, b, c), because that's the smallest number that is divisible by at least one of a, b, or c.
For example:
- If a = 2, b = 3, c = 5, the smallest ugly number is 2 because it is the smallest number divisible by a.
- If a = 4, b = 6, c = 8, the smallest ugly number is 4 because it is the minimum of (4, 6, 8).
This means our first ugly number is always min(a, b, c).
What is the Largest Possible Ugly Number?
In the worst-case scenario, the nth ugly number could be as large as 2 × 10⁹, as given in the problem constraints.
Thus, our search space for the nth ugly number is from min(a, b, c) to 2 × 10⁹.
We need to find numbers that are divisible by a, b, or c and count them until we reach the nth such number.
A number is ugly if it is divisible by a, b, or c.
- This means if we divide the number by a, b, or c, and there is no remainder, then it’s an ugly number.
We start from 1 and check each number:
- If it is divisible by a, b, or c, we count it.
- We keep counting until we reach the nth ugly number.
- As soon as we find the nth ugly number, we return it.
Let’s say n = 3, a = 2, b = 3, c = 5
We need to find the 3rd ugly number that is divisible by 2, 3, or 5.
We check numbers one by one:
- 1 → Not divisible by 2, 3, or 5
- 2 → Divisible by 2 (Count = 1)
- 3 → Divisible by 3 (Count = 2)
- 4 → Divisible by 2 (Count = 3) → Stop!
So, the 3rd ugly number is 4
Let's understand with an example:
Ugly Number III Example:
Let's do a concise dry run for n = 5, a = 2, b = 11, c = 13 using the simple approach:
We check numbers one by one and count the ones divisible by 2, 11, or 13.
1 is not divisible by 2, 11, or 13. (Count = 0)
2 is divisible by 2. (Count = 1)
3 is not divisible by 2, 11, or 13. (Count = 1)
4 is divisible by 2. (Count = 2)
5 is not divisible by 2, 11, or 13. (Count = 2)
6 is divisible by 2. (Count = 3)
7 is not divisible by 2, 11, or 13. (Count = 3)
8 is divisible by 2. (Count = 4)
9 is not divisible by 2, 11, or 13. (Count = 4)
10 is divisible by 2. (Count = 5) → Stop!
So, the 5th ugly number is 10
Steps to Implement the Solution:
- Initialize a count variable (count = 0)
This keeps track of how many ugly numbers we have found. - Iterate through numbers starting from 1 up to 2e9 (as per constraints)
We need to check each number one by one to see if it's ugly. - Check if the current number is divisible by a, b, or c
If num % a == 0 or num % b == 0 or num % c == 0, it is an ugly number. - Increase the count for every ugly number found
Keep counting until we reach the nth ugly number. - When count == n, return the current number (num)
This is the nth ugly number. - Return -1 as a fallback (though it should never reach here)
Since we know the answer always exists within the range.
Ugly Number III Leetcode Solution
Ugly Number III / Code Implementation
1. Ugly Number III solution in c++ Try on Compiler
class Solution {
public:
int nthUglyNumber(int n, int a, int b, int c) {
// Initialize a counter to keep track of how many ugly numbers we have found
int count = 0;
// Iterate through numbers starting from 1 up to 2e9 (as given in constraints)
for(int num = 1; num <= 2e9; num++)
{
// Check if the current number is divisible by a, b, or c
if (num % a == 0 || num % b == 0 || num % c == 0)
{
// Increase the count as we found an ugly number
count++;
// If we have found the nth ugly number, return it
if (count == n)
return num;
}
}
// Return -1 (should never reach here as the result is always within the given range)
return -1;
}
};
2. Ugly Number III solution in Java Try on Compiler
class Solution {
public int nthUglyNumber(int n, int a, int b, int c) {
// Initialize a counter to keep track of how many ugly numbers we have found
int count = 0;
// Iterate through numbers starting from 1 up to 2e9 (as given in constraints)
for (int num = 1; num <= 2_000_000_000; num++)
{
// Check if the current number is divisible by a, b, or c
if (num % a == 0 || num % b == 0 || num % c == 0)
{
// Increase the count as we found an ugly number
count++;
// If we have found the nth ugly number, return it
if (count == n)
return num;
}
}
// Return -1 (should never reach here as the result is always within the given range)
return -1;
}
}
3. Ugly Number III solution in Python Try on Compiler
class Solution:
def nthUglyNumber(self, n, a, b, c):
# Initialize a counter to keep track of how many ugly numbers we have found
count = 0
# Iterate through numbers starting from 1 up to 2e9 (as given in constraints)
for num in range(1, int(2e9) + 1):
# Check if the current number is divisible by a, b, or c
if num % a == 0 or num % b == 0 or num % c == 0:
# Increase the count as we found an ugly number
count += 1
# If we have found the nth ugly number, return it
if count == n:
return num
# Return -1 (should never reach here as the result is always within the given range)
return -1
4. Ugly Number III solution in Javascript Try on Compiler
/**
* @param {number} n
* @param {number} a
* @param {number} b
* @param {number} c
* @return {number}
*/
var nthUglyNumber = function (n, a, b, c) {
// Initialize a counter to keep track of how many ugly numbers we have found
let count = 0;
// Iterate through numbers starting from 1 up to 2e9 (as given in constraints)
for (let num = 1; num <= 2e9; num++) {
// Check if the current number is divisible by a, b, or c
if (num % a === 0 || num % b === 0 || num % c === 0) {
// Increase the count as we found an ugly number
count++;
// If we have found the nth ugly number, return it
if (count === n)
return num;
}
}
// Return -1 (should never reach here as the result is always within the given range)
return -1;
};Ugly Number III Complexity Analysis (brute force):
Time Complexity: O(n)
This approach linearly checks each number from 1 to 2e9 to find the nth ugly number that is divisible by a, b, or c.
In the worst case, the nth ugly number might be very large, meaning we need to iterate through almost all numbers up to 2e9.
So, in the worst case, the loop runs O(2e9) = O(n), where n is the largest number we check.
Space Complexity: O(1)
- Auxiliary Space Complexity: O(1)
The only additional space used is a few integer and long long variables (count, num).
Since these variables take O(1) space, the auxiliary space complexity is: O(1). - Total Space Complexity: O(1)
All computations are done in-place, and no additional memory is allocated dynamically.
Therefore, the total space complexity is O(1).
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(n), where n represents the worst-case number we need to iterate through before finding the nth ugly number. In this case, n can be as large as 2 × 10⁹ (2e9).
In the worst-case scenario, the algorithm iterates from 1 to n, leading to a time complexity of O(n).
This time complexity can become inefficient when n is large, particularly when n is close to its upper bound (2e9). In such cases, the algorithm may perform a large number of operations (nearly 2e9), making it impractical for large inputs.
This solution may not execute efficiently for all test cases, particularly when n is near its upper limit. While it may work for inputs with smaller values of n, it could exceed the time limits for large inputs where n is close to its maximum constraint.
In competitive programming environments, the typical time complexity limit is around 10⁶ operations per test case. Therefore, for inputs with large values of n, this time complexity could lead to inefficient execution.
How to optimize it?
In the previous approach, we checked every possible number starting from 1 and counted how many numbers were divisible by a, b, or c until we reached the nth ugly number. This gave us a time complexity of O(n), where n can be as large as 2 × 10⁹, making it extremely slow and prone to TLE (Time Limit Exceeded).
Now, let’s think about improving this.
The main issue was that we checked every number one by one to see if it was divisible by a, b, or c. Since n can be very large, iterating through all numbers takes too much time.
Can we make this part faster?
Yes! Here’s the hint:
We are searching for the nth ugly number, and we know that it lies somewhere between 1 and 2 × 10⁹ (since it is given in the constraints).
Now that we know the two endpoints, 1 and 2 × 10⁹, let's make a few observations:
- The data structure is sorted:
The set of numbers we consider (from 1 to 2 × 10⁹) is naturally sorted in increasing order. Since ugly numbers are just those numbers in this range that are divisible by a, b, or c, they too appear in sorted order. - The search space is monotonic:
Imagine you have a function that counts how many ugly numbers there are from 1 up to a number X. Let's call this function countUgly(X). The key idea is that as X increases, countUgly(X) will either stay the same or increase—it never decreases.
Think of it like climbing stairs:
- When you’re on a lower step, you’ve climbed fewer stairs.
- As you climb higher, you have climbed more stairs, or at least the same number if you pause for a moment.
Now, if for a certain number X you have already counted n ugly numbers (i.e., countUgly(X) ≥ n), then if you move to any number greater than X, you won’t lose any ugly numbers—you might even get more. This means every number after X will also have at least n ugly numbers up to that point.
Conversely, if at X you haven’t reached n ugly numbers, then any number smaller than X will also have even fewer ugly numbers.
This “one-way” behavior is what we call monotonicity. It allows us to use binary search because once we find a value of X that meets or exceeds the required count, we know that all larger values will also work, and if X doesn’t work, then no smaller number will work either.
- The middle element helps minimize or maximize the search space:
Instead of checking every possible number from 1 to 2 × 10⁹, we can take the middle value of our current search range and use our counting function to decide which half of the range to keep:
If the middle value mid produces a count that is at least n (i.e., we can construct at least n ugly numbers up to mid), then mid is a valid candidate. We then move to the left half of the range to see if there’s a smaller valid number.
If the count for mid is less than n, then mid is too small, and we must search in the right half for a number that produces enough ugly numbers.
Imagine plotting a graph with the potential values on the x-axis and the corresponding count of ugly numbers on the y-axis. As X increases, the count of ugly numbers increases monotonically. Before a certain threshold, the count is below n; after crossing that threshold, the count is at least n.
That threshold is exactly the nth ugly number.
Thus, by leveraging the sorted and monotonic properties of the range, we can apply binary search to quickly narrow down and pinpoint the smallest number X for which the count of ugly numbers ≤ X is at least n.
Ugly Number III Algorithm:
How to Count Ugly Numbers Efficiently?
To determine if a number X is at or beyond the position of the nth ugly number, we need to count how many ugly numbers exist that are ≤ X. Remember, an ugly number is any number that is divisible by at least one of a, b, or c. So, our goal is to count how many numbers from 1 to X are divisible by a, or b, or c.
Now, if we just add up:
- X / a (numbers divisible by a),
- X / b (numbers divisible by b),
- X / c (numbers divisible by c),
we run into a problem: some numbers are counted more than once. For example, if a = 2, b = 3, and c = 5, the number 6 is divisible by both 2 and 3. That means if we simply add those counts, 6 would be counted twice!
This is where the idea of the union of sets comes in. We want to count each number only once, even if it meets more than one condition. In set theory, when we want the union of multiple sets, we use the Inclusion-Exclusion Principle. The principle tells us that to get the correct count, we need to:
- Add the counts for each individual set.
- Subtract the counts of the numbers that appear in the intersections (i.e., numbers that are divisible by both a and b, both b and c, and both a and c).
- Add back the count for numbers that are divisible by all three (since they were subtracted too many times).
Let's consider three sets:
- A: Numbers ≤ X that are divisible by a
- B: Numbers ≤ X that are divisible by b
- C: Numbers ≤ X that are divisible by c
The formula for the union of these sets, A ∪ B ∪ C, is given by the Inclusion-Exclusion Principle:
|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |B ∩ C| - |A ∩ C| + |A ∩ B ∩ C|
Let’s find how many numbers from 1 to 30 are divisible by 2, 3, or 5.
Step 1: Count numbers divisible by each
- |A| = Numbers divisible by 2 → (2, 4, 6, ..., 30) → 15 numbers
- |B| = Numbers divisible by 3 → (3, 6, 9, ..., 30) → 10 numbers
- |C| = Numbers divisible by 5 → (5, 10, 15, ..., 30) → 6 numbers
Step 2: Subtract numbers counted twice (intersection of two sets)
- |A ∩ B| = Numbers divisible by LCM(2,3) = 6 → (6, 12, 18, 24, 30) → 5 numbers
- |B ∩ C| = Numbers divisible by LCM(3,5) = 15 → (15, 30) → 2 numbers
- |A ∩ C| = Numbers divisible by LCM(2,5) = 10 → (10, 20, 30) → 3 numbers
Step 3: Add back numbers removed too many times (intersection of all three sets)
- |A ∩ B ∩ C| = Numbers divisible by LCM(2,3,5) = 30 → (30) → 1 number
Final Calculation
∣A∪B∪C∣ = 15+10+6−5−2−3+1 = 22
Thus, 22 numbers from 1 to 30 are divisible by 2, 3, or 5.
In our context:
- Count of numbers ≤ X divisible by a = X / a
- Count of numbers ≤ X divisible by b = X / b
- Count of numbers ≤ X divisible by c = X / c
For the intersections, we use the Least Common Multiple (LCM):
- Count of numbers ≤ X divisible by both a and b = X / LCM(a, b)
- Count of numbers ≤ X divisible by both b and c = X / LCM(b, c)
- Count of numbers ≤ X divisible by both a and c = X / LCM(a, c)
- Count of numbers ≤ X divisible by a, b, and c = X / LCM(a, b, c)
Thus, the total count of ugly numbers up to X is calculated as:
countUgly(X) = (X / a) + (X / b) + (X / c) - (X / LCM(a, b)) - (X / LCM(b, c)) - (X / LCM(a, c)) + (X / LCM(a, b, c))
Using LCM is key because it gives us the smallest number that both a and b (or any pair/triple) divide into evenly. This helps ensure we count each eligible number only once, effectively giving us the union of the sets of numbers divisible by a, b, and c.
This efficient counting method lets us compute the number of ugly numbers up to any X in O(1) time. With this in hand, we can then apply binary search to quickly find the smallest X such that countUgly(X) ≥ n, which in turn gives us the nth ugly number.
Let us understand this with a video.
ugly-number-iii-optimal-approach-animation
Let's understand with an example:
Ugly Number III Example:
Let's perform a concise dry run of the binary search approach for:
Input: n = 5, a = 2, b = 11, c = 13
We need to find the 5th ugly number.
Step 1: Define Search Space
The ugly number is in the range [1, 2 × 10⁹].
We apply binary search on this range.
Step 2: Perform Binary SearchIteration 1:
- mid = (1 + 2e9) / 2 = 10⁹
- countUgly(10⁹) = (10⁹ / 2) + (10⁹ / 11) + (10⁹ / 13)
- (10⁹ / LCM(2,11)) - (10⁹ / LCM(11,13)) - (10⁹ / LCM(2,13))
+ (10⁹ / LCM(2,11,13)) - countUgly(10⁹) ≫ 5, so reduce search space to [1, 10⁹].
Iteration 2:
- mid = (1 + 10⁹) / 2 = 5 × 10⁸
- countUgly(5 × 10⁸) ≫ 5, so reduce search space to [1, 5 × 10⁸].
Iteration 3:
- mid = (1 + 5 × 10⁸) / 2 = 2.5 × 10⁸
- countUgly(2.5 × 10⁸) ≫ 5, so reduce search space to [1, 2.5 × 10⁸].
Fast-forwarding...
The search space shrinks progressively:
[1, 1.25 × 10⁸] → [1, 6.25 × 10⁷] → [1, 3.125 × 10⁷] → ... → [8, 12]
Eventually, binary search converges to X = 10, which is the 5th ugly number.
Final Answer: 10
How to code it up:
- Define Helper Functions
Implement GCD (Greatest Common Divisor) using the Euclidean Algorithm.
Implement LCM (Least Common Multiple) using the formula:
LCM(a, b) = (a * b) / GCD(a, b) (ensure division first to prevent overflow). - Count Ugly Numbers up to a Given Value (X)
- Use the Inclusion-Exclusion Principle to count numbers divisible by a, b, or c.
- Compute LCMs for pairs (a, b), (b, c), (a, c) and all three (a, b, c).
- Use the formula:
count(X) = (X / a) + (X / b) + (X / c) - (X / LCM(a, b)) - (X / LCM(b, c)) - (X / LCM(a, c)) + (X / LCM(a, b, c))
- Apply Binary Search to Find the Nth Ugly Number
- Initialize the search space:
- Low = min(a, b, c) (smallest ugly number).
- High = 2 × 10⁹ (given constraint).
- Perform binary search:
- Compute mid = (low + high) / 2.
- Count how many ugly numbers ≤ mid using countUglyNumbers(mid, a, b, c).
- If count >= n, store mid as a potential answer and move left (high = mid - 1).
- Else, move right (low = mid + 1).
- Return the smallest value where count is at least n.
Ugly Number III leetcode solution
Ugly Number III / Code Implementation
1. Ugly Number III solution in c++ Try on Compiler
class Solution {
// Function to calculate GCD (Greatest Common Divisor) using Euclidean algorithm
long long gcd(long long x, long long y) {
if (y == 0)
return x;
return gcd(y, x % y);
}
// Function to calculate LCM (Least Common Multiple) using the formula: LCM(a, b) = (a * b) / GCD(a, b)
long long lcm(long long x, long long y) {
return x / gcd(x, y) * y; // To avoid overflow, perform division first
}
// Function to count how many numbers up to 'm' are divisible by at least one of a, b, or c
long long countUglyNumbers(long long m, long long a, long long b, long long c) {
// Calculate LCM of pairwise combinations of a, b, and c
long long ab = lcm(a, b);
long long bc = lcm(b, c);
long long ac = lcm(a, c);
// Calculate LCM of all three numbers a, b, and c
long long abc = lcm(a, lcm(b, c));
// Apply Inclusion-Exclusion Principle to count numbers divisible by a, b, or c
return m / a + m / b + m / c - m / ab - m / bc - m / ac + m / abc;
}
public:
// Function to find the nth ugly number that is divisible by a, b, or c
int nthUglyNumber(int n, int a, int b, int c) {
// Initialize the search space with the smallest possible ugly number
long long low = min(a, min(b, c));
// The maximum possible answer is given in constraints (2 × 10^9)
long long high = 2e9;
// Variable to store the result
long long ans = -1;
// Perform Binary Search
while (low <= high) {
// Calculate the middle value of the search space
long long mid = low + (high - low) / 2;
// Count how many ugly numbers exist up to 'mid'
long long count = countUglyNumbers(mid, a, b, c);
// If there are at least 'n' ugly numbers, move left to find the smallest valid number
if (count >= n) {
ans = mid;
high = mid - 1;
}
// Otherwise, move right to increase the range
else {
low = mid + 1;
}
}
// Return the nth ugly number
return ans;
}
};
2. Ugly Number III solution in Java Try on Compiler
class Solution {
// Function to calculate GCD using Euclidean algorithm
private long gcd(long x, long y) {
if (y == 0)
return x;
return gcd(y, x % y);
}
// Function to calculate LCM using formula: LCM(a, b) = (a * b) / GCD(a, b)
private long lcm(long x, long y) {
return x / gcd(x, y) * y;
}
// Function to count how many numbers ≤ m are divisible by a, b, or c
private long countUglyNumbers(long m, long a, long b, long c) {
// Calculate pairwise LCM
long ab = lcm(a, b);
long bc = lcm(b, c);
long ac = lcm(a, c);
// Calculate LCM of all three numbers
long abc = lcm(a, lcm(b, c));
// Apply Inclusion-Exclusion Principle
return m / a + m / b + m / c - m / ab - m / bc - m / ac + m / abc;
}
// Function to find the nth ugly number
public int nthUglyNumber(int n, int a, int b, int c) {
// Initialize the search range
long low = Math.min(a, Math.min(b, c));
long high = (long) 2e9;
long ans = -1;
// Perform Binary Search
while (low <= high) {
// Find the middle value
long mid = low + (high - low) / 2;
// Count ugly numbers up to mid
long count = countUglyNumbers(mid, a, b, c);
// Adjust search range based on count
if (count >= n) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
// Return the nth ugly number
return (int) ans;
}
}
3. Ugly Number III solution in Python Try on Compiler
class Solution:
# Function to calculate GCD using Euclidean algorithm
def gcd(self, x, y):
if y == 0:
return x
return self.gcd(y, x % y)
# Function to calculate LCM using formula: LCM(a, b) = (a * b) // GCD(a, b)
def lcm(self, x, y):
return x // self.gcd(x, y) * y
# Function to count how many numbers ≤ m are divisible by a, b, or c
def countUglyNumbers(self, m, a, b, c):
# Calculate LCM pairwise
ab = self.lcm(a, b)
bc = self.lcm(b, c)
ac = self.lcm(a, c)
# Calculate LCM of all three numbers
abc = self.lcm(a, self.lcm(b, c))
# Apply Inclusion-Exclusion Principle
return m // a + m // b + m // c - m // ab - m // bc - m // ac + m // abc
# Function to find the nth ugly number
def nthUglyNumber(self, n, a, b, c):
# Initialize search range
low = min(a, b, c)
high = 2 * 10**9
ans = -1
# Perform Binary Search
while low <= high:
# Calculate mid value
mid = (low + high) // 2
# Count ugly numbers up to mid
count = self.countUglyNumbers(mid, a, b, c)
# Adjust search range
if count >= n:
ans = mid
high = mid - 1
else:
low = mid + 1
# Return the nth ugly number
return ans
4. Ugly Number III solution in Javascript Try on Compiler
/**
* Function to find the nth ugly number that is divisible by a, b, or c.
* Uses binary search and the inclusion-exclusion principle.
*
* @param {number} n - The nth ugly number to find.
* @param {number} a - First divisor.
* @param {number} b - Second divisor.
* @param {number} c - Third divisor.
* @return {number} - The nth ugly number.
*/
var nthUglyNumber = function(n, a, b, c) {
/**
* Helper function to calculate the GCD (Greatest Common Divisor)
* using the Euclidean algorithm.
*
* @param {number} x - First number.
* @param {number} y - Second number.
* @return {number} - The greatest common divisor of x and y.
*/
function gcd(x, y) {
if (y === 0) return x;
return gcd(y, x % y);
}
/**
* Helper function to calculate the LCM (Least Common Multiple)
* using the formula: LCM(a, b) = (a * b) / GCD(a, b)
*
* @param {number} x - First number.
* @param {number} y - Second number.
* @return {number} - The least common multiple of x and y.
*/
function lcm(x, y) {
return Math.floor((x / gcd(x, y)) * y);
}
/**
* Function to count how many numbers ≤ m are divisible by a, b, or c
* using the Inclusion-Exclusion Principle.
*
* @param {number} m - The number up to which we count ugly numbers.
* @param {number} a - First divisor.
* @param {number} b - Second divisor.
* @param {number} c - Third divisor.
* @return {number} - Count of numbers ≤ m that are divisible by a, b, or c.
*/
function countUglyNumbers(m, a, b, c) {
let ab = lcm(a, b);
let bc = lcm(b, c);
let ac = lcm(a, c);
let abc = lcm(a, lcm(b, c));
return Math.floor(m / a) + Math.floor(m / b) + Math.floor(m / c)
- Math.floor(m / ab) - Math.floor(m / bc) - Math.floor(m / ac)
+ Math.floor(m / abc);
}
// Initialize the search space:
// The lowest ugly number can be the smallest of a, b, or c.
let low = Math.min(a, b, c);
// The upper limit is given in the constraints (2 × 10^9)
let high = 2e9;
// Variable to store the result
let ans = -1;
// Perform Binary Search
while (low <= high) {
// Calculate the mid value
let mid = Math.floor((low + high) / 2);
// Count how many ugly numbers exist up to 'mid'
let count = countUglyNumbers(mid, a, b, c);
// If count is at least n, move left to find the smallest valid number
if (count >= n) {
ans = mid;
high = mid - 1;
}
// Otherwise, move right to find more ugly numbers
else {
low = mid + 1;
}
}
// Return the nth ugly number
return ans;
};
Complexity Analysis of Ugly Number III (binary search):
Time Complexity : O(1)
The solution primarily consists of two operations:
- Binary Search on the range [min(a, b, c), 2 × 10⁹]
- The search space is reduced by half in each iteration.
- The number of iterations required is O(log(2 × 10⁹)) ≈ O(log 10⁹) ≈ O(30).
- Counting Ugly Numbers in O(1) using the Inclusion-Exclusion Principle
- The count of ugly numbers is computed using the formula:
countUglyNumbers(m) = (m / a) + (m / b) + (m / c) - (m / lcm(a, b)) - (m / lcm(b, c)) - (m / lcm(a, c)) + (m / lcm(a, lcm(b, c))) - This involves a constant number of division and LCM calculations, all of which take O(1) time.
- The count of ugly numbers is computed using the formula:
Overall Time Complexity
- Binary Search: O(log max) = O(log 2 × 10⁹) ≈ O(30)
- Counting Ugly Numbers per Iteration: O(1) (constant time)
- Total Complexity: O(log max) × O(1) = O(log max) = O(30) ≈ O(1)
Since max = 2 × 10⁹, the worst case is about 30 iterations.
Space Complexity : O(1)
- Auxiliary Space Complexity: O(1)
The algorithm only uses a few integer and long long variables for binary search (low, high, mid, ans) and calculations (countUglyNumbers, lcm, gcd).
Therefore, the auxiliary space complexity is O(1). - Total Space Complexity: O(1)
The input constraints ensure that we only work with a few integer variables.
Therefore, the total space complexity is O(1).
Similar Problems
In many real-world problems, Math plays a crucial role in finding efficient solutions. For example, Binary Search is often used to optimize search-based problems, such as finding the right threshold in financial modeling or performance tuning. Combinatorics helps in counting and arranging possibilities, which is useful in fields like cryptography and network design. Meanwhile, Number Theory is fundamental in encryption algorithms, prime factorization, and modular arithmetic. By combining Math, Binary Search, Combinatorics, and Number Theory, we can solve complex computational problems efficiently across various domains.
Now that we have successfully tackled this problem, let's try similar problems.
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return the nth ugly number.
Given an array, arr[] of non-negative integers. The task is to return the maximum of j - i (i<=j) subjected to the constraint of arr[i] <= arr[j].