Find GCD:HCF of two numbers
Duration: 4 min
This video lesson is available to enrolled students.
Inside: a video lesson and guided study material.
Module outline
- Section A | English: Vocabulary, Comprehension / Reading Comprehension / Unseen Passages (Critical Reasoning) (Paragraph Questions), Preposition, Sentence Correction (Error Correction), Sentence Completion (Fill in the blanks), Articles, Sentence Re-arrangements (Para Jumbles) (Narrative Sequencing), Verbal Analogy (Word Based Analogy)
- Section A | Quant Aptitude: Ratio and Proportion (Ratios), Mixture and Alligation, Permutation and Combination, Number System, HCF LCM, Sequence and Series (Series), Speed Time and Distance, Arithmetic, Algebra, Powers and Exponents (Surds and Indices), Average, Age Problems, Percentage, Profit and Loss, Partnership, Time and Work, Simple Interest and Compound Interest, Mensuration and Geometry, Probability, Pipe and Cistern
- Section A | Reasoning: Series (Number and Letter Series) (Numerical Relations and Reasoning), Coding Decoding, Data Sufficiency, Calendar, Clock, Blood Relations, Directions (Direction Test), Seating Arrangements, Ranking, Order and Sequence, Puzzle Solving (Puzzles)
- Section B | C Programming: C Programming by Yash Sir, Coding Questions by Yash Sir
- Section B | Data Structures: Algorithm Analysis, Greedy Algorithms, Time Complexity Analysis, Sorting Algorithms, Introduction to DS, Array, Stack, Queue, Linked List, Tree, Graphs
- Section B | OOP (C++): Object Oriented Programming (OOPS), Programming in C++
- Section B | OS: Introduction to OS, Process Management, CPU Scheduling, Process Synchronization, Threads & Process Creation, Deadlock, Memory Management, Virtual Memory, Disc Scheduling, File Management, Windows OS
- Section B | Networking: Introduction to CN, Data Communication, DLL: Access Control, DLL: Flow Control, DLL: Error Control, DLL: Framing, Data Link Layer - Ethernet, Net Layer: IPv4 & Proto, Net Layer: IP Addressing, Net Layer:Routing Protocol, Transport Layer Services, TL: Congestion & UDP, Application Layer, Hardware basics
- Section B | AI & Big Data Basics: AI & ML by Arun Sir, Big Data Systems
- Section C | Digital Electronics: Digital Systems & Boolean Basics, Logic Gates & Hardware, Boolean Expression, Boolean Minimization, Combinational Circuit, Sequential Circuits, Number System, Number Representation, Analog-Digital Conversion
- Section A, C | Comp. Fundamentals, COA: Basics of COA, Floating Point Rep, Cache Memory Organization, Input Output Organisation, Pipelining, Instr Formats & Modes, Control Unit Design, Register Transfer and Microoperations, Multiprocessors, Programming the Basic Computer
- MOCK TEST:
AI summary & chapters
AI Summary
An AI-generated summary of this video lecture.
This video is a programming lecture from Knowledge Gate Eduventures, presented by Yash Jain Sir, a placement expert. The lesson focuses on solving the problem of finding the Greatest Common Divisor (GCD) of two numbers. The instructor first introduces the problem, showing a sample input of 12 and 18 and the expected output of 6. He then explains the mathematical concept of GCD using prime factorization, writing the prime factors of 12 as 2^2 * 3 and 18 as 2 * 3^2, and identifying the common factors to find the GCD as 2 * 3 = 6. The lecture transitions to the algorithmic solution, introducing the Euclidean Algorithm. The instructor writes the recursive C code for a function named 'gcd' that implements this algorithm, using the property that GCD(a, b) = GCD(b, a mod b). He demonstrates the recursive process with a call tree for GCD(18, 12), showing the steps: GCD(18, 12) -> GCD(12, 6) -> GCD(6, 0), which returns 6. The video concludes with the complete C program, including the main function that reads two integers and prints the result.
Chapters
0:00 – 2:00 00:00-02:00
The video begins with the 'KNOX MEEHEGATF' logo, which is a stylized version of 'KNOWLEDGE GATE'. It then transitions to a title slide for 'KNOWLEDGE GATE' with a branching diagram showing related channels like 'KG GATE & PLACEMENT PREP', 'KG CODING', and 'KG UGC NET COLLEGE PREP'. The main lecture starts with a problem statement on a digital blackboard: 'Q3: Write a program in c to find GCD of two numbers'. The input is defined as two positive integers separated by a space, and the output is the GCD. Two public test cases are shown: (20, 28) -> 4, and (98, 56) -> 14. The instructor, Yash Jain Sir, is visible in a small window. The topic is introduced as 'Logic' in a green box. The instructor begins to explain the concept of GCD by writing the prime factorization of 12 as 2^2 * 3 and 18 as 2 * 3^2 on the board.
2:00 – 4:09 02:00-04:09
The instructor continues to explain the GCD calculation by identifying the common prime factors of 12 and 18, which are 2 and 3, and multiplies them to get the GCD of 6. He then introduces the 'Euclidean Algorithm' as a more efficient method, writing 'Euclidean Alg' on the board. He explains that the algorithm is based on the property that GCD(a, b) = GCD(b, a mod b). He writes the recursive function signature 'int gcd(int a, int b)' and begins to write the code. He outlines the base cases: if a is 0, return b; if b is 0, return a. He then writes the recursive case: if a > b, return gcd(a-b, b). He draws a call tree on the board to illustrate the process for GCD(18, 12), showing the steps: GCD(18, 12) -> GCD(12, 6) -> GCD(6, 0), which returns 6. The video then shows the complete C code for the program, including the main function that reads two numbers and prints the GCD.
The video provides a comprehensive, step-by-step tutorial on finding the GCD of two numbers. It starts with a clear problem definition and examples, then explains the mathematical foundation using prime factorization. The core of the lesson is the introduction and implementation of the Euclidean Algorithm, a fundamental concept in computer science. The instructor effectively uses a digital blackboard to illustrate the logic, from the mathematical concept to the recursive code, and demonstrates the algorithm's execution with a call tree, making the abstract concept of recursion concrete for the viewer.

