Operate Numbers

Last Updated on March 25, 2022 by Ria Pathak

Concepts Used:

Mathematics

Difficulty Level:

Medium

Problem Statement (Simplified):

Perform following operations until one number becomes 0 and print the total number of operations.
1) Subtract larger number from smaller number.
2) Replace the larger number by difference and repeat the steps until any one of them becomes 0.

See original problem statement here

Test Case:

Input:
1
5 14

Output:
6

Explanation:
Lets solve this problem iteration by iteration :
1st iteration :
ba, so b = b - a = 13 - 5 = 8 and a = 5

2nd iteration :
ba, so b = b - a = 8 - 5 = 3 and a = 5  
As ab now, so we swap both, after swapping, a = 3 and b = 5  

3rd iteration :
ba, so b = b - a = 5 - 3 = 2 and a = 3  
As ab now, so we swap both, after swapping, a = 2 and b = 3  

4th iteration :
ba, so b = b - a = 3 - 2 = 1 and a = 2  
As ab now, so we swap both, after swapping, a = 1 and b = 2  

5th iteration :
ba, so b = b - a = 2 - 1 = 1 and a = 1  

6th iteration :
b=a, so b = b - a = 1 - 1 = 0, as b becomes 0, we print number of total iterations which resulted this, hence we achieved it at 6th iteration, so our answer is 6.

Solving Approach :

Bruteforce Approach:

1) We start a while loop and perform above-said operations one by one, and exits when any of number becomes 0.
2) We also count number of times while loop ran, after while loop end, we print the number of loops.
3) This approach takes longer times to run for larger inputs, as decreasing larger number by smaller number again and again takes large time. Its time complexity is O(M), where M is the greatest number of the two inputs. We can short the time of running by using mathematics which will be seen in next approach.

Efficient Approach:

1) When we get two numbers there can be two possible cases:

Case 1: If larger number is divisible by smaller number, then after steps any of number becomes 0.

Case 2: If larger number is not divisible by smaller number, then after steps smaller number becomes larger number, and smaller number is replaced by (larger number%smaller number).

2) We print the final steps after one number becomes 0.

EXAMPLE:

Case 1: If one number is divisible by another
Let’s take a=25 and b=5, if we continously subtract a from b, b becomes zero after 5 iterations i.e. ᵗʰ iteration, we can visualise this as,
1ˢᵗ iteration:

b = b - a = 25 -5 = 20, hence a = 5, b = 20

2ⁿᵈ iteration:

b = b - a = 20 -5 = 15, hence a = 5, b = 15

3ʳᵈ iteration:

b = b - a = 15 -5 = 10, hence a = 5, b = 10

4ᵗʰ iteration:

b = b - a = 10 -5 = 5, hence a = 5, b = 5

5ᵗʰ iteration:

b = b - a = 5 -5 = 0, hence a = 5, b = 0

Case 2: If no number is completely divisible by another
Let’s take a=27 and b=5, if we contiously subtract a from b, b is left with remainder of b/{a} after 5 iterations i.e.ᵗʰ iteration, we can visualise this as,
1ˢᵗ iteration:

b = b - a = 27 -5 = 22, hence a = 5, b = 22

2ⁿᵈ iteration:

b = b - a = 22 -5 = 17, hence a = 5, b = 17

3ʳᵈ iteration:

b = b - a = 17 -5 = 12, hence a = 5, b = 12

4ᵗʰ iteration:

b = b - a = 12 -5 = 7, hence a = 5, b = 7

5ᵗʰ iteration:

b = b - a = 7 - 5 = 2, hence a = 5, b = 2

Now, we can continue with swapped value of a and b, as remainder will always be lower than a, so we swap a and b making a = 2 and b = 5, and we again check both cases and apply steps until one of them becomes 0.

Solutions:

#include 

int main()
{

  int test;
  scanf("%d",&test);

  while(test--){

    int s,l;
    scanf("%d%d",&s,&l);

    int count = 0;

    while(s!=0 && l!=0){
      count+=l/s;
      int temp =  s;
      s = l%s;
      l = temp;
    }

    printf("%d\n",count);
  }

}

#include 
using namespace std;

int main()
{

  int test;
  cin>>test;

  while(test--){

    int s,l;
    cin>>s>>l;

    int count = 0;

    while(s!=0 && l!=0){
      count+=l/s;
      int temp =  s;
      s = l%s;
      l = temp;
    }

    cout<
						 

import java.util.*;
import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int test = sc.nextInt();

    while(test--!=0){

      int s = sc.nextInt(),l = sc.nextInt();

      int count = 0;

      while(s!=0 && l!=0){
        count+=l/s;
        int temp =  s;
        s = l%s;
        l = temp;
      }

      System.out.println(count);
    }

  }
}

for _ in range(int(input())):
	
	s, l = map(int, input().split())
	count = 0
	
	while(s != 0 and l != 0):
	
		count += l // s
		temp =  s
		s = l % s 
		l = temp

	print(count)

[forminator_quiz id="772"]

This article tried to discuss Mathematics. Hope this blog helps you understand and solve the problem. To practice more problems on Mathematics you can check out MYCODE | Competitive Programming.