LeetCode
  • Default
  • Learning Temp
  • Template
  • Copy of Template
  • CodeChef_Codeforces
    • Copy of Copy of Template
    • BitWise
      • Increasing Sequence with Fixed OR
    • Copy of Copy of Copy of Template
  • Array
    • GCD, Remainder etc, MAth
      • 1497. Check If Array Pairs Are Divisible by k
    • Easy
      • 1752. Check if Array Is Sorted and Rotated
      • 189. Rotate Array
      • 136. Single Number
      • 137. Single Number II
      • 260. Single Number III
      • Longest Sub-Array with Sum K
      • 2855. Minimum Right Shifts to Sort the Array
    • Medium
      • 75. Sort Colors/ Dutch National Flag
      • 169. Majority Element / Moore
      • 229. Majority Element II
      • 53. Maximum Subarray Sum / Kadane
      • 2149. Rearrange Array Elements by Sign
      • 31. Next Permutation
      • 2865. Beautiful Towers I
      • 1503. Last Moment Before All Ants Fall Out of a Plank
      • Longest Subarray With Sum K
      • Subarrays with XOR ‘K’
      • 3224. Minimum Array Changes to Make Differences Equal
      • Copy of Copy of Copy of Template
    • Hard
      • 15. 3Sum
      • 2862. Maximum Element-Sum of a Complete Subset of Indices
      • Number of Inversions
    • Sorting
      • Minimum Swaps to Sort
    • Prefix Sum
      • 2483. Minimum Penalty for a Shop
    • Two Pointer
      • 2824. Count Pairs Whose Sum is Less than Target
      • 88. Merge Sorted Array
      • 11. Container With Most Water
    • Matrix
      • 36. Valid Sudoku
      • 54. Spiral Matrix
      • 498. Diagonal Traverse
      • 1424. Diagonal Traverse II
    • Copy of Template
  • String
    • General
      • 1980. Find Unique Binary String
    • Easy
      • 14. Longest Common Prefix
      • 796. Rotate String
      • 459. Repeated Substring Pattern
      • 2833. Furthest Point From Origin
    • Medium
      • 2825. Make String a Subsequence Using Cyclic Increments
      • 5. Longest Palindromic Substring
      • 767. Reorganize String
      • 2840. Check if Strings Can be Made Equal With Operations II
      • 1653. Minimum Deletions to Make String Balanced
    • Hard
      • 686. Repeated String Match / Rabin Karp
      • 28. Find the Index of the First Occurrence in a String / KMP Algorithm
      • 214. Shortest Palindrome
      • 1392. Longest Happy Prefix
      • 1531. String Compression II
      • Copy of Copy of Copy of Template
    • Copy of Copy of Copy of Copy of Template
  • Hash & Map
    • 2829. Determine the Minimum Sum of a k-avoiding Array
    • 2834. Find the Minimum Possible Sum of a Beautiful Array
    • 621. Task Scheduler
    • 2365. Task Scheduler II
    • 1282. Group the People Given the Group Size They Belong To
    • 1647. Minimum Deletions to Make Character Frequencies Unique
    • 823. Binary Trees With Factors
  • Linked List
    • 86. Partition List
    • 138. Copy List with Random Pointer
    • Copy of Copy of Template
  • Binary Search
    • BS on 1D array
      • 34. Find First and Last Position of Element in Sorted Array
      • 162. Find Peak Element
      • 33. Search in Rotated Sorted Array
      • 81. Search in Rotated Sorted Array II
      • 540. Single Element in a Sorted Array
      • 287. Find the Duplicate Number
      • 1095. Find in Mountain Array
      • 2972. Count the Number of Incremovable Subarrays II
    • BS Over Answer Space/ Answer Space
      • Minimum Speed to Arrive on Time
      • Maximum Running Time of N Computers
      • 2616. Minimize the Maximum Difference of Pairs
      • 2861. Maximum Number of Alloys
      • 875. Koko Eating Bananas
      • 1482. Minimum Number of Days to Make m Bouquets
      • 1283. Find the Smallest Divisor Given a Threshold
      • 1011. Capacity To Ship Packages Within D Days / Book Allocation Problem
      • 1539. Kth Missing Positive Number
      • 1552. Magnetic Force Between Two Balls / Aggressive Cows
      • 410. Split Array Largest Sum
      • 4. Median of Two Sorted Arrays
      • K-th Element of Two Sorted Arrays
      • 2560. House Robber IV
      • 378. Kth Smallest Element in a Sorted Matrix
      • 786. K-th Smallest Prime Fraction
      • Copy of Copy of Copy of Template
    • BS on 2D Arrays
      • 2643. Row With Maximum Ones
      • 74. Search a 2D Matrix
      • 240. Search a 2D Matrix II
      • 1901. Find a Peak Element II
    • Copy of Copy of Copy of Template
  • Bit Masking
    • 338. Counting Bits
    • 2857. Count Pairs of Points With Distance k
    • 1239. Maximum Length of a Concatenated String with Unique Characters
    • 1457. Pseudo-Palindromic Paths in a Binary Tree
    • Copy of Copy of Copy of Copy of Template
  • Stack
    • Monotonic Stack
      • 84. Largest Rectangle in Histogram
      • 85. Maximal Rectangle
      • 316. Remove Duplicate Letters
      • 503. Next Greater Element II
      • 907. Sum of Subarray Minimums
      • 402. Remove K Digits
    • 1106. Parsing A Boolean Expression
  • Sliding Window
    • Medium
      • 3. Longest Substring Without Repeating Characters
      • 1004. Max Consecutive Ones III
      • 930. Binary Subarrays With Sum
      • 1248. Count Number of Nice Subarrays
      • 1358. Number of Substrings Containing All Three Characters
      • 1423. Maximum Points You Can Obtain from Cards
      • 992. Subarrays with K Different Integers
      • 2841. Maximum Sum of Almost Unique Subarray
      • 1658. Minimum Operations to Reduce X to Zero
      • 2875. Minimum Size Subarray in Infinite Array
      • 560. Subarray Sum Equals K
      • 3306. Count of Substrings Containing Every Vowel and K Consonants II
    • Hard
      • 76. Minimum Window Substring
      • 30. Substring with Concatenation of All Words
      • 42. Trapping Rain Water
    • 2831. Find the Longest Equal Subarray
    • 1838. Frequency of the Most Frequent Element
    • Copy of Copy of Copy of Template
  • Prefix & Suffix
    • 2874. Maximum Value of an Ordered Triplet II
  • Heaps and Priority Queue
    • 215. Kth Largest Element in an Array
    • 295. Find Median from Data Stream
    • 480. Sliding Window Median
    • 2842. Count K-Subsequences of a String With Maximum Beauty
    • 2856. Minimum Array Length After Pair Removals
    • 846. Hand of Straights
    • 1642. Furthest Building You Can Reach
    • 692. Top K Frequent Words
    • 1094. Car Pooling
    • Hard
      • 355. Design Twitter
      • Line sweep Technique / 2251. Number of Flowers in Full Bloom
      • 1425. Constrained Subsequence Sum
    • Copy of Copy of Template
  • Greedy
    • Medium
      • 45. Jump Game II
      • 56. Merge Intervals
      • 57. Insert Interval
    • Copy of Copy of Template
  • Trees
    • Binary Tree
      • Easy
        • 110. Balanced Binary Tree
        • 543. Diameter of Binary Tree
      • Medium
        • 654. Maximum Binary Tree
        • 103. Binary Tree Zigzag Level Order Traversal
        • 236. Lowest Common Ancestor of a Binary Tree / 235. Lowest Common Ancestor of a Binary Search Tree
        • 987. Vertical Order Traversal of a Binary Tree
      • Hard
        • 124. Binary Tree Maximum Path Sum
        • 987. Vertical Order Traversal of a Binary Tree
        • 662. Maximum Width of Binary Tree
        • 863. All Nodes Distance K in Binary Tree
        • 222. Count Complete Tree Nodes
        • 105. Construct Binary Tree from Preorder and Inorder Traversal
        • 106. Construct Binary Tree from Inorder and Postorder Traversal
        • 297. Serialize and Deserialize Binary Tree
        • 114. Flatten Binary Tree to Linked List
    • BST
      • 653. Two Sum IV - Input is a BST
      • 98. Validate Binary Search Tree
      • 1008. Construct Binary Search Tree from Preorder Traversal
      • 99. Recover Binary Search Tree
      • 450. Delete Node in a BST
      • 173. Binary Search Tree Iterator
    • Copy of Copy of Template
    • Copy of Copy of Copy of Template
  • Graph
    • General
      • 1615. Maximal Network Rank
      • 2973. Find Number of Coins to Place in Tree Nodes
    • Topo Sort
      • Topological sort
      • 2050. Parallel Courses III
    • Shortest Path
      • Dijkstra Algorithm
      • Bellman Ford
      • 787. Cheapest Flights Within K Stops
      • Floyd Warshall
      • 1976. Number of Ways to Arrive at Destination
      • 2976. Minimum Cost to Convert String I
    • MST/ Disjoint Set
      • Minimum Spanning Tree (Prims)
      • Union by Rank/ Size
      • Kruskal Algorithm
      • 827. Making A Large Island
      • 778. Swim in Rising Water
    • Other Algo
      • 1192. Critical Connections in a Network / Find Bridges
      • Articulation Point - I
    • DFS/BFS
      • 3249. Count the Number of Good Nodes
    • Copy of Copy of Template
  • Recursion & Backtracking
    • Subsequence Pattern
      • 39. Combination Sum
      • 40. Combination Sum II
      • 216. Combination Sum III
      • 377. Combination Sum IV
    • 46. Permutations
    • 2850. Minimum Moves to Spread Stones Over Grid
    • 1922. Count Good Numbers
    • 78. Subsets
    • Copy of Copy of Copy of Copy of Template
  • Dynamic Programming
    • General
      • Predict the Winner
      • 808. Soup Servings
      • 1359. Count All Valid Pickup and Delivery Options
      • 799. Champagne Tower
      • 746. Min Cost Climbing Stairs
      • 779. K-th Symbol in Grammar
      • 2742. Painting the Walls
      • 3250. Find the Count of Monotonic Pairs I
    • Tree DP
      • 96. Unique Binary Search Trees
      • 95. Unique Binary Search Trees II
    • DP + Binary Search
      • 2830. Maximize the Profit as the Salesman
      • 646. Maximum Length of Pair Chain
    • DP on Grids
      • Unique Paths
      • 63. Unique Paths II
    • DP on Strings
      • Wildcard Matching
      • 712. Minimum ASCII Delete Sum for Two Strings
      • 139. Word Break
      • 2707. Extra Characters in a String
      • 2844. Minimum Operations to Make a Special Number
      • Longest Common Substring
      • 516. Longest Palindromic Subsequence
    • Partition Equal Subset Sum
    • DP on LIS
      • 300. Longest Increasing Subsequence
      • 368. Largest Divisible Subset
      • 673. Number of Longest Increasing Subsequence
      • 2826. Sorting Three Groups
      • 1048. Longest String Chain
      • 1458. Max Dot Product of Two Subsequences
      • 2900. Longest Unequal Adjacent Groups Subsequence I
      • Copy of Copy of Template
    • DP on Stocks
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Best Time to Buy and Sell Stock III
      • 188. Best Time to Buy and Sell Stock IV
      • 309. Best Time to Buy and Sell Stock with Cooldown
      • 714. Best Time to Buy and Sell Stock with Transaction Fee
    • MCM DP | Partition DP
      • Matrix Chain Multiplication
      • 1547. Minimum Cost to Cut a Stick
      • 312. Burst Balloons
      • 132. Palindrome Partitioning II
      • 1043. Partition Array for Maximum Sum
      • 2369. Check if There is a Valid Partition For The Array
    • DP on Squares
      • 1277. Count Square Submatrices with All Ones
    • Copy of Copy of Template
  • Trie
    • 208. Implement Trie (Prefix Tree)
    • 1698-Number of Distinct Substrings in a String Using Trie
    • 421. Maximum XOR of Two Numbers in an Array
    • 1707. Maximum XOR With an Element From Array
  • Insights & new Learnings
    • Find One string inside other
    • Heap Custom Sort comparator
    • Ceil Function (Alternative)
    • Comparator Sort
    • GCD of two numbers
    • Convert String to integer in Any base and vise versa
    • Seive of Erathostenis
    • Atmost Approach for Sliding Window
    • Copy of Copy of Copy of Copy of Learning Temp
Powered by GitBook
On this page
  • Problem Statement
  • Intuition
  • Links
  • Video Links
  • Approach 1:
  • Approach 2:
  • Approach 3:
  • Approach 4:
  • Similar Problems
  1. Insights & new Learnings

GCD of two numbers

PreviousComparator SortNextConvert String to integer in Any base and vise versa

Last updated 1 year ago

Problem Statement

Intuition

Appraoch:

GCD (a,b) = GCd(a-b, b) = Gcd(a%b, b) where a>b
The moment we get one of zero we return other


Time Comp = O(logbase(phi){min(a,b)})

Links

Video Links

Approach 1:

C++

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems

https://www.youtube.com/watch?v=1xNbjMdbjug&ab_channel=takeUforward