{"id":757,"date":"2020-06-11T10:14:43","date_gmt":"2020-06-11T10:14:43","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=757"},"modified":"2022-03-25T10:44:57","modified_gmt":"2022-03-25T10:44:57","slug":"operate-numbers","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/operate-numbers\/","title":{"rendered":"Operate Numbers"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used:<\/h3>\n
\n

Mathematics<\/p>\n<\/blockquote>\n

Difficulty Level:<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

Perform following operations until one number becomes 0 and print the total number of operations.
\n1) Subtract larger number<\/code> from smaller number<\/code>.
\n2) Replace the larger number<\/code> by difference and repeat the steps until any one of them becomes 0. <\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Test Case:<\/h4>\n
Input:\n1\n5 14\n\nOutput:\n6\n\nExplanation:\nLets solve this problem iteration by iteration :\n1st iteration :\nba, so b = b - a = 13 - 5 = 8 and a = 5\n\n2nd iteration :\nba, so b = b - a = 8 - 5 = 3 and a = 5  \nAs ab now, so we swap both, after swapping, a = 3 and b = 5  \n\n3rd iteration :\nba, so b = b - a = 5 - 3 = 2 and a = 3  \nAs ab now, so we swap both, after swapping, a = 2 and b = 3  \n\n4th iteration :\nba, so b = b - a = 3 - 2 = 1 and a = 2  \nAs ab now, so we swap both, after swapping, a = 1 and b = 2  \n\n5th iteration :\nba, so b = b - a = 2 - 1 = 1 and a = 1  \n\n6th iteration :\nb=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.<\/code><\/pre>\n
Solving Approach :<\/h4>\n
Bruteforce Approach<\/strong>:<\/p>\n
\n
1) We start a while loop and perform above-said operations one by one, and exits when any of number becomes 0<\/code>.
\n2) We also count number of times while loop ran, after while loop end, we print the number of loops.
\n3) 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)<\/code>, where M<\/code> 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. <\/p>\n<\/blockquote>\n
Efficient Approach<\/strong>:<\/p>\n
\n
1) When we get two numbers there can be two possible cases:<\/p>\n<\/blockquote>\n
Case 1:<\/em><\/strong> If larger number<\/code> is divisible by smaller number<\/code>, then after  steps any of number becomes 0.<\/p>\n
Case 2:<\/em><\/strong> If larger number<\/code> is not divisible by smaller number<\/code>, then after  steps smaller number<\/code> becomes larger number<\/code>, and  smaller number<\/code> is replaced by (larger number<\/code>%smaller number<\/code>).<\/p>\n
\n
2) We print the final steps after one number becomes 0.<\/p>\n<\/blockquote>\n
EXAMPLE:<\/h3>\n
\n
Case 1: If one number is divisible by another<\/em><\/strong>
\nLet’s take a=25<\/code> and b=5<\/code>, if we continously subtract a<\/code> from b<\/code>, b<\/code> becomes zero after 5<\/code> iterations i.e. \u1d57\u02b0  iteration, we can visualise this as,
\n1\u02e2\u1d57<\/code> iteration:<\/em><\/strong>  <\/p>\n
b = b - a = 25 -5 = 20<\/code>, hence a = 5, b = 20<\/code><\/p>\n
2\u207f\u1d48<\/code> iteration:<\/em><\/strong>  <\/p>\n
b = b - a = 20 -5 = 15<\/code>, hence a = 5, b = 15<\/code>  <\/p>\n
3\u02b3\u1d48<\/code> iteration:<\/em><\/strong>  <\/p>\n
b = b - a = 15 -5 = 10<\/code>, hence a = 5, b = 10<\/code>  <\/p>\n
4\u1d57\u02b0<\/code> iteration:<\/em><\/strong>  <\/p>\n
b = b - a = 10 -5 = 5<\/code>, hence a = 5, b = 5<\/code>  <\/p>\n
5\u1d57\u02b0<\/code> iteration:<\/em><\/strong><\/p>\n
b = b - a = 5 -5 = 0<\/code>, hence a = 5, b = 0<\/code>  <\/p>\n
Case 2: If no number is completely divisible by another<\/em><\/strong>
\nLet’s take a=27<\/code> and b=5<\/code>, if we contiously subtract a<\/code> from b<\/code>, b<\/code> is left with remainder of b<\/code>\/{a} after 5<\/code> iterations i.e.\u1d57\u02b0 iteration, we can visualise this as,
\n1\u02e2\u1d57<\/code> iteration:<\/em><\/strong>  <\/p>\n
b = b - a = 27 -5 = 22<\/code>, hence a = 5, b = 22<\/code><\/p>\n
2\u207f\u1d48<\/code> iteration:<\/em><\/strong>  <\/p>\n
b = b - a = 22 -5 = 17<\/code>, hence a = 5, b = 17<\/code>  <\/p>\n
3\u02b3\u1d48<\/code> iteration:<\/em><\/strong>  <\/p>\n
b = b - a = 17 -5 = 12<\/code>, hence a = 5, b = 12<\/code>  <\/p>\n
4\u1d57\u02b0<\/code> iteration:<\/em><\/strong>  <\/p>\n
b = b - a = 12 -5 = 7<\/code>, hence a = 5, b = 7<\/code>  <\/p>\n
5\u1d57\u02b0<\/code> iteration:<\/em><\/strong><\/p>\n
b = b - a = 7 - 5 = 2<\/code>, hence a = 5, b = 2<\/code><\/p>\n
Now, we can continue with swapped value of a<\/code> and b<\/code>, as remainder will always be lower than a<\/code>, so we swap a<\/code> and b<\/code> making a = 2<\/code> and b = 5<\/code>, and we again check both cases and apply steps until one of them becomes 0<\/code>.<\/p>\n<\/blockquote>\n
Solutions:<\/h3>\n\t\t\t\t\t\t