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
- Quantitative Ability: Speed Mathematics and Basic Mathematics, Percentage, Ratio and Proportion (Ratios), Average, Profit and Loss, Simple Interest and Compound Interest, Time and Work, Pipe and Cistern, Speed Time and Distance, Number System, HCF LCM, Data Interpretation, Age Problems, Mixture and Alligation, Partnership, Algebra, Sequence and Series (Series), Mensuration and Geometry, Arithmetic
- Reasoning Ability: Puzzle Solving (Puzzles), Seating Arrangements, Coding Decoding, Blood Relations, Directions (Direction Test), Syllogisms, Data Sufficiency, Ranking, Order and Sequence, Series (Number and Letter Series) (Numerical Relations and Reasoning), Logical Sequence Of Words, Calendar, Clock, Cubes & Dices, Analytical Reasoning (Counting Figures Reasoning), Data Arrangement, Non Verbal Reasoning (Spatial Aptitude) (Spatial Reasoning) (Visual Reasoning), Deductive and Inductive Reasoning (Logical Deduction and Induction) (Prepositional Reasoning)
- Verbal Ability: Comprehension / Reading Comprehension / Unseen Passages (Critical Reasoning) (Paragraph Questions), Cloze Test (Cloze Passage), Sentence Re-arrangements (Para Jumbles) (Narrative Sequencing), Vocabulary, Sentence Completion (Fill in the blanks), Active Passive Voice (Voice), Direct and Indirect Speech, Subject Verb Agreement (Verb Noun Agreement), Tenses, Preposition, Articles, Sentence Correction (Error Correction)
- Programming Basics (MCQs + Interview): C Programming by Yash Sir, Programming in C++, Java, Python for Placements by Yash Sir
- OOPs (MCQs + Interview): Object Oriented Programming (OOPS)
- DBMS (MCQs + Interview): Basics of DBMS, ER Diagram, Relational Model & Functional Dependencies, Keys & Integrity Constraints, Normalization (1NF - BCNF), Transaction Management, Decomposition Properties & 4NF, Concurrency Control, Database Recovery, File Organization & Indexing, Relational Algebra, Database Security & Authorization
- SQL (MCQs + Interview): SQL
- Operating Systems (MCQs + Interview): Introduction to OS, Process Management, CPU Scheduling, Deadlock, Threads & Process Creation, Memory Management, Virtual Memory, Process Synchronization, Disc Scheduling, File Management, Security
- Computer Networks (MCQs + Interview): 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, Network Security, Cloud Computing and IoT, Cyber and Info Security
- Coding: Coding Questions by Yash Sir
- HR Interview: MR & HR Interview Preparation
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.

