Pattern 18 of 22

Math and Number Theory Pattern: Template + 485 LeetCode Problems

Find the closed form, the invariant, or the modular identity — and skip the loop entirely.

Get Stealth Interview
Easy
121
Medium
244
Hard
120
Time
O(log n) or O(1)

What the math and number theory pattern is

Some problems have no algorithm worth writing because they have a formula. The tell is a statement about digits, divisors, remainders, or counting arrangements, together with a constraint large enough — 10⁹ and up — that any loop over the input range is hopeless by construction. The recurring tools are small in number: the Euclidean algorithm for the greatest common divisor, which underlies fractions, cycles and repeating patterns; modular arithmetic, where addition and multiplication distribute over the modulus so you can reduce at every step instead of overflowing; a sieve when many primes below a bound are needed rather than one primality test; and fast exponentiation, which raises to the nth power in log n multiplications by squaring. The other half of this pattern is not a technique but a habit: compute the first six answers by hand, look for the pattern, then prove it. An invariant — a quantity the operations never change — usually collapses a simulation into a one-line check.

When to use it

  • The constraints are far too large to iterate, so the answer must be computed rather than searched.
  • The statement is about digits, divisibility, remainders, primes, or gcd.
  • You are counting arrangements and the answer is requested modulo 10⁹ + 7.
  • A simulation is described but some quantity is clearly conserved throughout it.

The math and number theory template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 485 problems listed below.

PythonMath and Number Theory template
def gcd(a, b):
    while b:
        a, b = b, a % b       # gcd(a, b) == gcd(b, a mod b), and b strictly shrinks
    return a

def power_mod(base, exponent, mod):
    result = 1
    base %= mod
    while exponent:
        if exponent & 1:                  # this bit of the exponent is set
            result = result * base % mod
        base = base * base % mod          # square for the next bit
        exponent >>= 1
    return result

Complexity characteristics

Time
O(log n) or O(1)
Auxiliary space
O(1)

The point of the pattern is that there is no loop over the input: a closed form is O(1), the Euclidean algorithm for a greatest common divisor is O(log min(a, b)), and fast exponentiation raises to the nth power in O(log n) multiplications. A sieve is the exception that costs real time and memory — O(n log log n) to build and O(n) to hold — and is only worth it when many primes below a bound are needed rather than a single primality test.

Eyes only

Meet the math and number theory problem you did not practise.

In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.

Get Stealth InterviewSee pricing

All 485 math and number theory LeetCode problems

Every problem in the library the math and number theory pattern applies to, grouped by LeetCode's own difficulty rating. 413 of the 485 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related LeetCode topics

Easy (121)

Easy problems
No.Problem
0009Palindrome Number
0013Roman to Integer
0066Plus One
0067Add Binary
0069Sqrt(x)
0070Climbing Stairs
0168Excel Sheet Column Title
0171Excel Sheet Column Number
0202Happy Number
0231Power of Two
0258Add Digits
0263Ugly Number
0268Missing Number
0292Nim Game
0326Power of Three
0342Power of Four
0367Valid Perfect Square
0405Convert a Number to Hexadecimal
0412Fizz Buzz
0415Add Strings
0441Arranging Coins
0492Construct the Rectangle
0504Base 7
0507Perfect Number
0509Fibonacci Number
0598Range Addition II
0628Maximum Product of Three Numbers
0728Self Dividing Numbers
1071Greatest Common Divisor of Strings
1137N-th Tribonacci Number
0762Prime Number of Set Bits in Binary Representation
0800Similar RGB ColorPremium
0812Largest Triangle Area
0836Rectangle Overlap
0883Projection Area of 3D Shapes
0892Surface Area of 3D Shapes
0908Smallest Range I
0914X of a Kind in a Deck of Cards
0976Largest Perimeter Triangle
0989Add to Array-Form of Integer
1025Divisor Game
1030Matrix Cells in Distance Order
1037Valid Boomerang
1056Confusing NumberPremium
1085Sum of Digits in the Minimum NumberPremium
1103Distribute Candies to People
1118Number of Days in a MonthPremium
1134Armstrong NumberPremium
1154Day of the Year
1175Prime Arrangements
1180Count Substrings with Only One Distinct LetterPremium
1185Day of the Week
1217Minimum Cost to Move Chips to The Same Position
1228Missing Number In Arithmetic ProgressionPremium
1232Check If It Is a Straight Line
1252Cells with Odd Values in a Matrix
1266Minimum Time Visiting All Points
1271HexspeakPremium
1281Subtract the Product and Sum of Digits of an Integer
1290Convert Binary Number in a Linked List to Integer
1295Find Numbers with Even Number of Digits
1304Find N Unique Integers Sum up to Zero
1317Convert Integer to the Sum of Two No-Zero Integers
1323Maximum 69 Number
1342Number of Steps to Reduce a Number to Zero
1360Number of Days Between Two Dates
1399Count Largest Group
1427Perform String ShiftsPremium
1486XOR Operation in an Array
1512Number of Good Pairs
1518Water Bottles
1523Count Odd Numbers in an Interval Range
1588Sum of All Odd Length Subarrays
1688Count of Matches in Tournament
1716Calculate Money in Leetcode Bank
1742Maximum Number of Balls in a Box
1812Determine Color of a Chessboard Square
1822Sign of the Product of an Array
1837Sum of Digits in Base K
1863Sum of All Subset XOR Totals
1903Largest Odd Number in String
1925Count Square Sum Triples
1952Three Divisors
1979Find Greatest Common Divisor of Array
2119A Number After a Double Reversal
2160Minimum Sum of Four Digit Number After Splitting Digits
2169Count Operations to Obtain Zero
2180Count Integers With Even Digit Sum
2235Add Two Integers
2269Find the K-Beauty of a Number
2409Count Days Spent Together
2413Smallest Even Multiple
2427Number of Common Factors
2455Average Value of Even Numbers That Are Divisible by Three
2469Convert the Temperature
2481Minimum Cuts to Divide a Circle
2485Find the Pivot Integer
2520Count the Digits That Divide a Number
2525Categorize Box According to Criteria
2535Difference Between Element Sum and Digit Sum of an Array
2544Alternating Digit Sum
2549Count Distinct Numbers on Board
2566Maximum Difference by Remapping a Digit
2578Split With Minimum Sum
2582Pass the Pillow
2591Distribute Money to Maximum Children
2600K Items With the Maximum Sum
2614Prime In Diagonal
2651Calculate Delayed Arrival Time
2652Sum Multiples
2729Check if The Number is Fascinating
2739Total Distance Traveled
2748Number of Beautiful Pairs
2769Find the Maximum Achievable Number
2806Account Balance After Rounded Purchase
2843Count Symmetric Integers
2864Maximum Odd Binary Number
2894Divisible and Non-divisible Sums Difference
2928Distribute Candies Among Children I
2946Matrix Similarity After Cyclic Shifts
2965Find Missing and Repeated Values

Medium (244)

Medium problems
No.Problem
0002Add Two Numbers
0007Reverse Integer
0012Integer to Roman
0029Divide Two Integers
0043Multiply Strings
0048Rotate Image
0050Pow(x, n)
0062Unique Paths
0089Gray Code
0096Unique Binary Search Trees
0150Evaluate Reverse Polish Notation
0166Fraction to Recurring Decimal
0172Factorial Trailing Zeroes
0189Rotate Array
0204Count Primes
0223Rectangle Area
0227Basic Calculator II
0241Different Ways to Add Parentheses
0264Ugly Number II
0279Perfect Squares
0313Super Ugly Number
0319Bulb Switcher
0343Integer Break
0357Count Numbers with Unique Digits
0365Water and Jug Problem
0368Largest Divisible Subset
0371Sum of Two Integers
0372Super Pow
0375Guess Number Higher or Lower II
0380Insert Delete GetRandom O(1)
0382Linked List Random Node
0384Shuffle an Array
0390Elimination Game
0396Rotate Function
0398Random Pick Index
0400Nth Digit
0423Reconstruct Original Digits from English
0445Add Two Numbers II
0447Number of Boomerangs
0453Minimum Moves to Equal Array Elements
0462Minimum Moves to Equal Array Elements II
0464Can I Win
0470Implement Rand10() Using Rand7()
0477Total Hamming Distance
0478Generate Random Point in a Circle
0486Predict the Winner
0497Random Point in Non-overlapping Rectangles
0519Random Flip Matrix
0523Continuous Subarray Sum
0528Random Pick with Weight
0537Complex Number Multiplication
0539Minimum Time Difference
0553Optimal Division
0556Next Greater Element III
0592Fraction Addition and Subtraction
0593Valid Square
0633Sum of Square Numbers
0640Solve the Equation
06502 Keys Keyboard
0667Beautiful Arrangement II
0670Maximum Swap
0672Bulb Switcher II
0738Monotone Increasing Digits
0973K Closest Points to Origin
0294Flip Game IIPremium
0356Line ReflectionPremium
0360Sort Transformed ArrayPremium
0369Plus One Linked ListPremium
0469Convex PolygonPremium
0573Squirrel SimulationPremium
0625Minimum FactorizationPremium
0634Find the Derangement of An ArrayPremium
06514 Keys KeyboardPremium
0750Number Of Corner RectanglesPremium
0754Reach a Number
0775Global and Local Inversions
0779K-th Symbol in Grammar
0781Rabbits in Forest
0788Rotated Digits
0789Escape The Ghosts
0808Soup Servings
0837New 21 Game
0840Magic Squares In Grid
0858Mirror Reflection
0866Prime Palindrome
0869Reordered Power of 2
0877Stone Game
0910Smallest Range II
0932Beautiful Array
0939Minimum Area Rectangle
0957Prison Cells After N Days
0963Minimum Area Rectangle II
0970Powerful Integers
0991Broken Calculator
1006Clumsy Factorial
1015Smallest Integer Divisible by K
1017Convert to Base -2
1033Moving Stones Until Consecutive
1040Moving Stones Until Consecutive II
1041Robot Bounded In Circle
1058Minimize Rounding Error to Meet TargetPremium
1073Adding Two Negabinary Numbers
1093Statistics from a Large Sample
1104Path In Zigzag Labelled Binary Tree
1131Maximum of Absolute Value Expression
1140Stone Game II
1201Ugly Number III
1215Stepping NumbersPremium
1227Airplane Seat Assignment Probability
1230Toss Strange CoinsPremium
1237Find Positive Integer Solution for a Given Equation
1238Circular Permutation in Binary Representation
1247Minimum Swaps to Make Strings Equal
1248Count Number of Nice Subarrays
1256Encode NumberPremium
1276Number of Burgers with No Waste of Ingredients
1344Angle Between Hands of a Clock
1352Product of the Last K Numbers
1362Closest Divisors
1390Four Divisors
1401Circle and Rectangle Overlapping
1414Find the Minimum Number of Fibonacci Numbers Whose Sum Is K
1432Max Difference You Can Get From Changing an Integer
1442Count Triplets That Can Form Two Arrays of Equal XOR
1447Simplified Fractions
1492The kth Factor of n
1513Number of Substrings With Only 1s
1524Number of Sub-arrays With Odd Sum
1538Guess the Majority in a Hidden ArrayPremium
1551Minimum Operations to Make Array Equal
1561Maximum Number of Coins You Can Get
1573Number of Ways to Split a String
1577Number of Ways Where Square of Number Is Equal to Product of Two Numbers
1621Number of Sets of K Non-Overlapping Line Segments
1628Design an Expression Tree With Evaluate FunctionPremium
1634Add Two Polynomials Represented as Linked ListsPremium
1641Count Sorted Vowel Strings
1648Sell Diminishing-Valued Colored Balls
1680Concatenation of Consecutive Binary Numbers
1685Sum of Absolute Differences in a Sorted Array
1686Stone Game VI
1690Stone Game VII
1753Maximum Score From Removing Stones
1759Count Number of Homogenous Substrings
1780Check if Number is a Sum of Powers of Three
1802Maximum Value at a Given Index in a Bounded Array
1806Minimum Number of Operations to Reinitialize a Permutation
1814Count Nice Pairs in an Array
1823Find the Winner of the Circular Game
1828Queries on Number of Points Inside a Circle
1860Incremental Memory Leak
1878Get Biggest Three Rhombus Sums in a Grid
1884Egg Drop With 2 Eggs and N Floors
1904The Number of Full Rounds You Have Played
1908Game of NimPremium
1922Count Good Numbers
1927Sum Game
1954Minimum Garden Perimeter to Collect Enough Apples
1969Minimum Non-Zero Product of the Array Elements
1999Smallest Greater Multiple Made of Two DigitsPremium
2001Number of Pairs of Interchangeable Rectangles
2028Find Missing Observations
2029Stone Game IX
2033Minimum Operations to Make a Uni-Value Grid
2038Remove Colored Pieces if Both Neighbors are the Same Color
2048Next Greater Numerically Balanced Number
2063Vowels of All Substrings
2083Substrings That Begin and End With the Same LetterPremium
2101Detonate the Maximum Bombs
2110Number of Smooth Descent Periods of a Stock
2125Number of Laser Beams in a Bank
2128Remove All Ones With Row and Column FlipsPremium
2139Minimum Moves to Reach Target Score
2152Minimum Number of Lines to Cover PointsPremium
2162Minimum Cost to Set Cooking Time
2165Smallest Value of the Rearranged Number
2177Find Three Consecutive Integers That Sum to a Given Number
2178Maximum Split of Positive Even Integers
2189Number of Ways to Build House of CardsPremium
2195Append K Integers With Minimal Sum
2198Number of Single Divisor TripletsPremium
2217Find Palindrome With Fixed Length
2221Find Triangular Sum of an Array
2240Number of Ways to Buy Pens and Pencils
2249Count Lattice Points Inside a Circle
2266Count Number of Texts
2280Minimum Lines to Represent a Line Chart
2310Sum of Numbers With Units Digit K
2317Maximum XOR After Operations
2348Number of Zero-Filled Subarrays
2358Maximum Number of Groups Entering a Competition
2364Count Number of Bad Pairs
2393Count Strictly Increasing SubarraysPremium
2396Strictly Palindromic Number
2400Number of Ways to Reach a Position After Exactly k Steps
2417Closest Fair IntegerPremium
2436Minimum Split Into Subarrays With GCD Greater Than OnePremium
2442Count Number of Distinct Integers After Reverse Operations
2443Sum of Number and Its Reverse
2447Number of Subarrays With GCD Equal to K
2450Number of Distinct Binary Strings After Applying OperationsPremium
2457Minimum Addition to Make Integer Beautiful
2464Minimum Subarrays in a Valid SplitPremium
2470Number of Subarrays With LCM Equal to K
2489Number of Substrings With Fixed RatioPremium
2495Number of Subarrays Having Even ProductPremium
2505Bitwise OR of All Subsequence SumsPremium
2507Smallest Value After Replacing With Sum of Prime Factors
2513Minimize the Maximum of Two Arrays
2521Distinct Prime Factors of Product of Array
2523Closest Prime Numbers in Range
2527Find Xor-Beauty of Array
2539Count the Number of Good SubsequencesPremium
2541Minimum Operations to Make Array Equal II
2550Count Collisions of Monkeys on a Polygon
2572Count the Number of Square-Free Subsets
2575Find the Divisibility Array of a String
2579Count Total Number of Colored Cells
2597The Number of Beautiful Subsets
2598Smallest Missing Non-negative Integer After Operations
2601Prime Subtraction Operation
2607Make K-Subarray Sums Equal
2638Count the Number of K-Free SubsetsPremium
2654Minimum Number of Operations to Make All Array Elements Equal to 1
2698Find the Punishment Number of an Integer
2745Construct the Longest New String
2750Ways to Split Array Into Good Subarrays
2761Prime Pairs With Target Sum
2802Find The K-th Lucky NumberPremium
2807Insert Greatest Common Divisors in Linked List
2816Double a Number Represented as a Linked List
2829Determine the Minimum Sum of a k-avoiding Array
2834Find the Minimum Possible Sum of a Beautiful Array
2844Minimum Operations to Make a Special Number
2847Smallest Number With Given Digit ProductPremium
2849Determine if a Cell Is Reachable at a Given Time
2929Distribute Candies Among Children II
2930Number of Strings Which Can Be Rearranged to Contain Substring
2939Maximum Xor Product
2947Count Beautiful Substrings I
2961Double Modular Exponentiation
2967Minimum Cost to Make Array Equalindromic
2979Most Expensive Item That Can Not Be BoughtPremium
2992Number of Self-Divisible PermutationsPremium

Hard (120)

Hard problems
No.Problem
0060Permutation Sequence
0149Max Points on a Line
0224Basic Calculator
0233Number of Digit One
0273Integer to English Words
0282Expression Add Operators
0335Self Crossing
0381Insert Delete GetRandom O(1) - Duplicates allowed
0391Perfect Rectangle
0458Poor Pigs
0479Largest Palindrome Product
0483Smallest Good Base
0564Find the Closest Palindrome
0587Erect the Fence
0668Kth Smallest Number in Multiplication Table
067924 Game
0710Random Pick with Blacklist
0296Best Meeting PointPremium
0660Remove 9Premium
0770Basic Calculator IV
0772Basic Calculator IIIPremium
0780Reaching Points
0782Transform to Chessboard
0793Preimage Size of Factorial Zeroes Function
0805Split Array With Same Average
0810Chalkboard XOR Game
0829Consecutive Numbers Sum
0843Guess the Word
0878Nth Magical Number
0887Super Egg Drop
0891Sum of Subsequence Widths
0899Orderly Queue
0902Numbers At Most N Given Digit Set
0906Super Palindromes
0913Cat and Mouse
0920Number of Music Playlists
0927Three Equal Parts
0952Largest Component Size by Common Factor
0964Least Operators to Express Number
0972Equal Rational Numbers
0996Number of Squareful Arrays
1012Numbers With Repeated Digits
1067Digit Count in RangePremium
1088Confusing Number IIPremium
1183Maximum Number of OnesPremium
1199Minimum Time to Build BlocksPremium
1250Check If It Is a Good Array
1259Handshakes That Don't CrossPremium
1307Verbal Arithmetic Puzzle
1330Reverse Subarray To Maximize Array Value
1359Count All Valid Pickup and Delivery Options
1363Largest Multiple of Three
1406Stone Game III
1453Maximum Number of Darts Inside of a Circular Dartboard
1467Probability of a Two Boxes Having The Same Number of Distinct Balls
1478Allocate Mailboxes
1510Stone Game IV
1515Best Position for a Service Centre
1563Stone Game V
1569Number of Ways to Reorder Array to Get Same BST
1610Maximum Number of Visible Points
1622Fancy Sequence
1627Graph Connectivity With Threshold
1643Kth Smallest Instructions
1728Cat and Mouse II
1735Count Ways to Make Array With Product
1739Building Boxes
1766Tree of Coprimes
1776Car Fleet II
1799Maximize Score After N Operations
1808Maximize Number of Nice Divisors
1819Number of Different Subsequences GCDs
1830Minimum Number of Operations to Make String Sorted
1835Find XOR Sum of All Pairs Bitwise AND
1840Maximum Building Height
1862Sum of Floored Pairs
1866Number of Ways to Rearrange Sticks With K Sticks Visible
1872Stone Game VIII
1896Minimum Cost to Change the Final Value of Expression
1916Count Ways to Build Rooms in an Ant Colony
1924Erect the Fence IIPremium
1956Minimum Time For K Virus Variants to SpreadPremium
1994The Number of Good Subsets
1998GCD Sort of an Array
2005Subtree Removal Game with Fibonacci TreePremium
2019The Score of Students Solving Math Expression
2081Sum of k-Mirror Numbers
2117Abbreviating the Product of a Range
2147Number of Ways to Divide a Long Corridor
2183Count Array Pairs Divisible by K
2197Replace Non-Coprime Numbers in Array
2338Count the Number of Ideal Arrays
2344Minimum Deletions to Make Array Divisible
2366Minimum Replacements to Sort the Array
2376Count Special Integers
2440Create Components With Same Value
2514Count Anagrams
2524Maximum Frequency Score of a SubarrayPremium
2543Check if Point Is Reachable
2584Split the Array to Make Coprime Products
2613Beautiful PairsPremium
2647Color the Triangle RedPremium
2681Power of Heroes
2709Greatest Common Divisor Traversal
2719Count of Integers
2790Maximum Number of Groups With Increasing Length
2818Apply Operations to Maximize Score
2827Number of Beautiful Integers in the Range
2842Count K-Subsequences of a String With Maximum Beauty
2851String Transformation
2862Maximum Element-Sum of a Complete Subset of Indices
2867Count Valid Paths in a Tree
2868The Wording GamePremium
2912Number of Ways to Reach Destination in the GridPremium
2927Distribute Candies Among Children IIIPremium
2941Maximum GCD-Sum of a SubarrayPremium
2949Count Beautiful Substrings II
2954Count the Number of Infection Sequences
2963Count the Number of Good Partitions
2999Count the Number of Powerful Integers

Math and Number Theory pattern FAQ

What is the math and number theory pattern?

Some problems have no algorithm worth writing because they have a formula. The tell is a statement about digits, divisors, remainders, or counting arrangements, together with a constraint large enough — 10⁹ and up — that any loop over the input range is hopeless by construction.

How many LeetCode problems use the math and number theory pattern?

This page lists 485 LeetCode problems that the math and number theory pattern applies to: 121 Easy, 244 Medium and 120 Hard. 413 of them carry a complete Python solution with complexity analysis.

What is the time complexity of the math and number theory pattern?

O(log n) or O(1) time and O(1) space. The point of the pattern is that there is no loop over the input: a closed form is O(1), the Euclidean algorithm for a greatest common divisor is O(log min(a, b)), and fast exponentiation raises to the nth power in O(log n) multiplications. A sieve is the exception that costs real time and memory — O(n log log n) to build and O(n) to hold — and is only worth it when many primes below a bound are needed rather than a single primality test.

When should I use the math and number theory pattern in an interview?

The constraints are far too large to iterate, so the answer must be computed rather than searched. The statement is about digits, divisibility, remainders, primes, or gcd.

Which math and number theory problem should I start with?

LeetCode 9. Palindrome Number is the lowest-numbered Easy problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.

What patterns are related to math and number theory?

Bit Manipulation, Dynamic Programming, Greedy, Prefix Sum. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.

More ways in: all 22 patterns, the curated study lists, or the full problem list.