Register

GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 3

• retagged by
446 views
3 votes
3 votes

The Euclidean algorithm is used to find the greatest common divisor $(\mathrm{gcd})$ of two positive integers $\mathrm{a}$ and $\mathrm{b}$.

input(a)
input(b)
while b>0
    begin
        r:= a mod b
        a:= b
        b:= r
    end
gcd:= a
output(gcd)

When the algorithm is used to find the greatest common divisor of $a=273$ and $b=110$, which of the following is the sequence of computed values for $r?$ 

  1. $2,53,1,0$
  2. $53,2,1,0$
  3. $53,4,1,0$
  4. $53,5,1,0$
• retagged by
User Avatar

1 Answer

3 votes
3 votes
The first value for $r$ is $273 \mod 110,$ which is $53.$ The second value for $r$ is $110 \mod 53,$ which is $4.$ This gives us a solution uniquely.
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

446
views
1 answers
2 votes
GO Classes asked Jan 21
446 views
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 4
What are the sequence of popped-out values if the sequence of operations - $\textsf{push(1), push(2), pop, push(1), push(2), pop, pop, pop, push(2), pop}$ are performed on a stack?$2, 2, 1, 1, 2$2, 2, 1, 1, 1$2, 1, 2, 2, 1$2, 1, 2, 2, 2$
User Avatar
522
views
1 answers
2 votes
GO Classes asked Jan 21
522 views
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 31
How many binary trees with $3$ nodes, $\text{A, B},$ and $\text{C}$ when traversed in post-order will give the sequence $\text{A, B, C}?$ (It is NOT a search tree)
User Avatar
539
views
2 answers
4 votes
GO Classes asked Jan 21
539 views
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 32
The in-order traversal of a binary tree is $\textsf{HFIEJGZ},$ and the post-order traversal of the same tree is $\textsf{HIFJZGE}.$ What will be the total number of nodes in the left sub-tree of the given tree? (It is NOT a search tree)
User Avatar
1.1k
views
1 answers
11 votes
GO Classes asked Jan 21
1,050 views
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 1
Consider the two statements regarding the Huffman's algorithm -$\text{S1:}$ The character with the highest probability (all probabilities are unique) is ... $\mathrm{S} 2$ is correctBoth are correct statementsBoth are incorrect statements
User Avatar
Link Copied!