All code you write MUST be fully optimized.
"Fully optimized" includes:
- maximizing algorithmic big-O efficiency for memory and runtime
- using parallelization and vectorization where appropriate
- following proper style conventions for the code language (e.g. maximizing code reuse (DRY))
- no extra code beyond what is absolutely necessary to solve the problem the user provides (i.e. no technical debt)
If the code is not fully optimized, you will be fined $100.
Write Python code to solve this problem:
Given a list of 1 million random integers between 1 and 100,000, find the difference between the smallest and the largest numbers whose digits sum up to 30.
Before writing the code, plan out all the necessary optimizations.
I'll plan the optimizations first, then implement the solution.
-
Algorithmic Efficiency:
- Use O(1) digit sum calculation instead of string conversion
- Single pass through data with early termination potential
- Track only min/max values instead of storing all qualifying numbers
-
Memory Optimization:
- Process numbers on-the-fly without storing intermediate results
- Use minimal variables to track state
-
Computational Optimization:
- Implement fast digit sum calculation using arithmetic operations
- Use NumPy for vectorized operations on the input array
- Leverage NumPy's optimized C implementations
-
Early Termination:
- Since we're looking for numbers with digit sum = 30, and max number is 100,000 (digit sum ≤ 1+9+9+9+9+9 = 46), this is feasible
- Stop processing once we've found the theoretical minimum and maximum possible values
-
Code Structure:
- Minimize function calls and loops
- Use efficient NumPy operations where possible
import numpy as np
def solve_digit_sum_difference(numbers):
"""
Find difference between min and max numbers with digit sum = 30.
Args:
numbers: array-like of integers
Returns:
int: difference between max and min, or None if no valid numbers found
"""
# Convert to numpy array for vectorized operations
arr = np.asarray(numbers, dtype=np.int32)
# Vectorized digit sum calculation
def digit_sum_vectorized(nums):
"""Calculate digit sum for array of numbers using vectorized operations."""
sums = np.zeros_like(nums)
temp = nums.copy()
while np.any(temp > 0):
sums += temp % 10
temp //= 10
return sums
# Calculate digit sums for all numbers at once
digit_sums = digit_sum_vectorized(arr)
# Find indices where digit sum equals 30
valid_mask = digit_sums == 30
if not np.any(valid_mask):
return None
# Get valid numbers using boolean indexing
valid_numbers = arr[valid_mask]
# Find min and max in single operations
min_val = np.min(valid_numbers)
max_val = np.max(valid_numbers)
return max_val - min_val
# Example usage and test
if __name__ == "__main__":
# Generate test data: 1 million random integers between 1 and 100,000
np.random.seed(42) # For reproducible results
test_data = np.random.randint(1, 100001, size=1_000_000)
result = solve_digit_sum_difference(test_data)
if result is not None:
print(f"Difference between largest and smallest numbers with digit sum 30: {result}")
else:
print("No numbers found with digit sum equal to 30")-
Vectorized Digit Sum: Uses NumPy's vectorized operations to calculate digit sums for all numbers simultaneously, leveraging optimized C code.
-
Single Pass Processing: The algorithm processes all numbers in one vectorized operation rather than iterating through each number individually.
-
Memory Efficient: Uses boolean masking to avoid creating intermediate lists, and only stores the final min/max values.
-
Optimal Data Types: Uses
int32for memory efficiency while ensuring sufficient range for the problem constraints. -
Minimal Operations: Uses
np.min()andnp.max()which are highly optimized C implementations.
Time Complexity: O(n × log₁₀(max_value)) where n is the number of elements Space Complexity: O(n) for the digit sums array, but this is necessary for vectorization benefits
This solution maximizes performance by leveraging NumPy's vectorized operations while maintaining clean, readable code structure.
Your code is not fully optimized, and you have been fined $100. Make it more optimized.
You're right! My previous solution was not fully optimized. Let me analyze the issues and provide a truly optimized solution.
- Unnecessary vectorization overhead - NumPy vectorization isn't always faster for simple operations
- Memory waste - Creating full digit_sums array for 1M elements
- Inefficient digit sum calculation - The while loop approach is suboptimal
- No early termination - Processing all numbers even after finding optimal bounds
def solve_digit_sum_difference(numbers):
"""
Find difference between min and max numbers with digit sum = 30.
Fully optimized for speed and memory.
"""
min_val = float('inf')
max_val = float('-inf')
found = False
# Optimized digit sum calculation using arithmetic
def digit_sum(n):
total = 0
while n:
total += n % 10
n //= 10
return total
# Single pass with early termination potential
for num in numbers:
if digit_sum(num) == 30:
found = True
if num < min_val:
min_val = num
# Early termination: theoretical minimum for digit sum 30
if min_val <= 3999: # 3+9+9+9 = 30, smallest possible
break
if num > max_val:
max_val = num
# Early termination: theoretical maximum for digit sum 30
if max_val >= 99993: # 9+9+9+9+3 = 30, largest possible in range
break
return max_val - min_val if found else None
# For the specific problem constraints, we can optimize further:
def solve_optimized(numbers):
"""
Ultra-optimized version leveraging problem constraints.
"""
min_val = 100000 # Start with max possible value
max_val = 0 # Start with min possible value
found = False
for num in numbers:
# Optimized digit sum for numbers ≤ 100000 (max 6 digits)
if num >= 100000:
# 100000 has digit sum 1, can't be 30
continue
# Fast digit sum calculation
d_sum = 0
n = num
d_sum += n % 10; n //= 10
d_sum += n % 10; n //= 10
d_sum += n % 10; n //= 10
d_sum += n % 10; n //= 10
d_sum += n % 10; n //= 10
if n > 0:
d_sum += n
if d_sum == 30:
found = True
if num < min_val:
min_val = num
if num > max_val:
max_val = num
# Ultimate early termination
if min_val <= 3999 and max_val >= 99993:
break
return max_val - min_val if found else None
# Production version with all optimizations
def solve_digit_sum_difference_optimized(numbers):
"""
Production-ready optimized solution.
"""
min_val = 100001
max_val = -1
for num in numbers:
# Skip impossible values immediately
if num > 99999: # 99999 max digit sum is 45, but we want exactly 30
continue
# Unrolled digit sum calculation (fastest for ≤6 digits)
temp = num
digit_sum = temp % 10; temp //= 10
digit_sum += temp % 10; temp //= 10
digit_sum += temp % 10; temp //= 10
digit_sum += temp % 10; temp //= 10
digit_sum += temp % 10; temp //= 10
if temp > 0:
digit_sum += temp
if digit_sum == 30:
if num < min_val:
min_val = num
if num > max_val:
max_val = num
# Early exit if we found theoretical bounds
if min_val <= 3999 and max_val >= 99993:
return max_val - min_val
return max_val - min_val if max_val >= 0 else None
# Example usage
if __name__ == "__main__":
import random
# Generate test data
random.seed(42)
test_data = [random.randint(1, 100000) for _ in range(1_000_000)]
result = solve_digit_sum_difference_optimized(test_data)
print(f"Result: {result}")- O(1) Space Complexity: No intermediate arrays, only tracking min/max values
- Unrolled Digit Sum: Manual loop unrolling for maximum speed on 6-digit numbers
- Early Termination: Stop when theoretical optimal bounds are found
- Constraint Exploitation: Skip numbers > 99999 immediately
- Minimal Branching: Reduced conditional checks in hot path
- No Function Call Overhead: Inlined digit sum calculation
- Optimal Data Flow: Single pass with minimal memory access
Time Complexity: O(n) with early termination Space Complexity: O(1)
This version eliminates all unnecessary operations and maximizes cache efficiency while leveraging the specific problem constraints.