Loops 3
If you have gone through the previous articles, I can confidently say that now we are ready to solve most of the problems based on the loops concept. We have covered various approaches and techniques required to solve these problems. In this article, we will do some good problems based on loops.
Suggestion : First try to do the questions on your own. Give yourself some time and resist the temptation to look at the solution quickly. After giving your best shot, you can definitely go through the solution.✌️
Now, Let's start with the questions with our weapon. (A pen and paper)
Problem 1: LCM of two Numbers
Write a C++ program to input two numbers from user and find LCM (Lowest Common Multiple).
Input
Input number1: 5
Input number2: 10Output
LCM = 10Approach
If we know what is LCM, Can we give it a try? Always spend some time with the question to improve problem solving skills. 😄
What is LCM?
LCM is the smallest positive integer that exactly divides two or more numbers.
Let's understand this with an analogy.
Imagine you have two friends, Alice and Bob, who have different hobbies and engage in activities at regular intervals. Alice goes for a swim every 4 days, and Bob goes for a run every 6 days. Now, you want to find a day when both Alice and Bob are engaged in their activities on the same day.
To find this common day, you would look for the least common multiple of 4 and 6. It's the smallest number that is a multiple of both 4 and 6. In this case, the LCM is 12 because both 4 and 6 exactly divide 12 (4 x 3 = 12 and 6 x 2 = 12). So, after 12 days, Alice will have gone for a swim three times, and Bob will have gone for a run twice, and they will both be engaged in their activities on the same day.
Intuition
The LCM will be a multiple of both numbers. Don't you think we should find the maximum of both numbers and check it's multiples one by one and see if they are multiples of the other number as well? You can find the LCM by considering the multiples of the larger number until you find one that is also a multiple of the smaller number.
But, why check the multiples of the maximum of two numbers, not the smaller one? So, it's not about checking all multiples of the larger number; rather, it's about finding the first common multiple of both numbers, starting with the multiples of the larger number. The LCM will indeed be a multiple of both numbers, but checking the multiples of the larger number helps identify the smallest such multiple efficiently. Don't you think the number of iterations will be less if we do it this way?
Now, give it a try.
Explanation/Steps
- Input two numbers from the user. Store them in some variable say num1 and num2.
- Find the maximum between two numbers. Store the result in some variable, say max. Maximum is used to generate the next multiple which must be common to both.
- If max is exactly divisible by both numbers. Then you get your answer, store max to some variable say lcm = max. If LCM is found then terminate from the loop.
- If max is not divisible by both numbers. Then generate the next multiple of max.
- Repeat steps 2 to 3 step till LCM is found.
Solution
#include <iostream>
using namespace std;
int main()
{
int i, num1, num2, max, lcm=1;
/* Input two numbers from user */
cout << "Enter any two numbers to find LCM: ";
cin >> num1 >> num2;
/* Find maximum between num1 and num2 using ter */
if(num1 > num2){
max = num1;
}
else{
max = num2;
}
/* First multiple to be checked */
i = max;
/* Run loop indefinitely till LCM is found */
while(true)
{
if(i % num1 == 0 && i % num2 == 0)
{
/*
* If 'i' divides both 'num1' and 'num2'
* then 'i' is the LCM.
*/
lcm = i;
/* Terminate the loop after LCM is found */
break;
}
/*
* If LCM is not found then generate next
* multiple of max between both numbers
*/
i += max;
}
cout << "Lcm = " << lcm;
return 0;
}Problem 2: HCF(GCD) of two numbers
Write a C++ program to input two numbers from the user and find HCF (Highest Common Factor) / GCD (Greatest Common Divisor).
Input
Input number1: 12
Input number2: 30Output
HCF is 6Approach
If we know what is HCF, Can we give it a try? 😄
What is HCF?
HCF (Highest Common Factor) is the greatest number that divides exactly two or more numbers. HCF is also known as GCD (Greatest Common Divisor) or GCF (Greatest Common Factor).
In simple terms, we can say that HCF is used to find the largest number that divides two or more numbers without leaving a remainder.
Intuition
Now you know what is HCF. So, tell me one thing what can be the maximum value of HCF? It will be the minimum of the two given numbers. Also, What will be the minimum value of HCF? It will be 1 guys because 1 will be a factor the any two given numbers.
So, We will find which is the largest integer between 1 and the minimum of two numbers that is a factor of both the given numbers. This number will be our HCF.
Now we have enough hints, give it a try.
Explanation/Steps
- Input two numbers from the user. Store them in some variable say num1 and num2.
- Declare and initialize a variable to hold hcf i.e.
hcf = 1. - Find the minimum between the given two numbers. Store the result in some variable say min.
- Run a loop from 1 to min, and increment the loop by 1 in each iteration. The loop structure should look like for(i=1; i<=min; i++).
- Inside the loop check if i is a factor of two numbers i.e. if i exactly divides the given two numbers num1 and num2 then set i as HCF i.e.
hcf = i.
Solution 1
#include <iostream>
using namespace std;
int main()
{
int i, num1, num2, min, hcf=1;
/* Input two numbers from user */
cout << "Enter any two numbers to find HCF: ";
cin >> num1 >> num2;
/* Find minimum between two numbers */
if(num1 < num2){
min = num1;
}
else{
min = num2;
}
for(i=1; i<=min; i++)
{
/* If i is factor of both number */
if(num1 % i == 0 && num2 % i == 0)
{
hcf = i;
}
}
cout << "HCF is " << hcf;
return 0;
}Let's see one more approach to solve this !! In this approach, we will traverse from the minimum of two numbers to 1 and as soon as we find the common factor, we will break from the loop. This way we are trying to reduce our iterations for finding the HCF. ✌️
Solution 2
#include <iostream>
using namespace std;
int main()
{
int i, num1, num2, min, hcf=1;
/* Input two numbers from user */
cout << "Enter any two numbers to find HCF: ";
cin >> num1 >> num2;
/* Find minimum between two numbers */
if(num1 < num2){
min = num1;
}
else{
min = num2;
}
for(i = min; i >= 1; i--)
{
/* If i is factor of both number */
if(num1 % i == 0 && num2 % i == 0)
{
hcf = i;
break;
}
}
cout << "HCF is " << hcf;
return 0;
}Learn More 🙌
Can we find the HCF of two numbers if we know LCM? Yes, we can.
The formula that shows the relationship between their LCM and HCF is LCM (a,b) × HCF (a,b) = a × b.
Problem 3: Check Armstrong Numbers
Write a C++ program to input a number from the user and check whether the given number is an Armstrong number or not.
Input
Enter the number: 371Output
371 is armstrong numberApproach
To solve this question, we will first see what is an Armstrong number. When we see this term for the first time we don't know what it means. At least I did not know.
What is a Armstrong Number?
An Armstrong number is a n-digit number that is equal to the sum of the nth power of its digits.
For example –
6 = 61 = 6
371 = 33 + 73 + 13 = 371
Intuition
Try to break down this problem into steps.
- First, calculate the number of digits. Let's say it is n.
- Then one by one get the digits and calculate the power of the digit with the exponent as the total number of digits(which is n). After this update the sum.
- Finally, can we now check whether the number is Armstrong or not by equating the sum that we have calculated in the previous step with the number?
One function that you may require while solving this question is pow( ).
The pow( ) function returns the result of the first argument raised to the power of the second argument. This function is defined in the cmath header file. In C++, pow(a, b) = a ^b.
Please give it a try now.
Explanation/Steps
- Input a number from the user. Store it in some variable say num. Make a temporary copy of the value to some another variable for calculation purposes, say
originalNum = num. - Count total digits in the given number, and store the result in a variable say digits.
- Initialize another variable to store the sum of the power of its digits, say
sum = 0. - Run a loop till
num > 0. The loop structure should look likewhile(num > 0). - Inside the loop, find the last digit of the num. Store it in a variable say
lastDigit = num % 10. - Now comes the real calculation to find the sum of the power of digits. Perform
sum = sum + pow(lastDigit, digits). - Since the last digit of num is processed. Hence, remove the last digit by performing
num = num / 10. - After loop check
if(originalNum == sum), then it is Armstrong number otherwise not.
Solution
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int originalNum, num, lastDigit, sum;
int digits = 0;
/* Input number from user */
cout << "Enter any number to check Armstrong number: ";
cin >> num;
sum = 0;
/* Copy the value of num for processing */
originalNum = num;
/* Find total digits in num */
if (num == 0){
digits = 1;
}
while (num != 0) {
num = num / 10;
++digits;
}
// Copy the value of originalNum to num
//As num has been modified while calculating number of digits */
num = originalNum;
/* Calculate sum of power of digits */
while(num > 0)
{
/* Extract the last digit */
lastDigit = num % 10;
/* Compute sum of power of last digit */
sum = sum + pow(lastDigit, digits); //In C++, pow(a, b) = a ^ b.
/* Remove the last digit */
num = num / 10;
}
/* Check for Armstrong number */
if(originalNum == sum)
{
cout << "It is ARMSTRONG NUMBER";
}
else
{
cout << "It is NOT ARMSTRONG NUMBER";
}
return 0;
}
Problem 4: Print Armstrong Numbers
Write a C++ program to print all Armstrong numbers between 1 to n where n is the input given by the user.
Input
Enter the number n: 1000Output
Armstrong numbers between 1 to 1000 are:
1, 2, 3, 4, 5, 6, 7, 8, 9, 370, 371, 407Approach
If you have gone through the previous question i.e. problem 3, this question would be easy to solve as we already know the concept. Give it an honest try without looking at the solution. ✌️😄
Intuition
We have to print Armstrong numbers between 1 and n. So, we can simply run a loop from 1 to n and print those numbers which are Armstrong. We already have seen how to check whether a number is Armstrong or not in Problem 3. Sounds easy Right?
Note: We also have a Log-based Solution to count digits in an integer. We can use log10(logarithm of base 10) to count the number of digits of positive numbers (logarithm is not defined for negative numbers).
Digit count of N = upper bound of log10(N).
To find the digits we have used: digits=(int) log 10(num)+1 in our solution. Why have we done (int) and what is that ?? It is known as typecasting in C++. The ans could be a double and that's why we are converting it to int using the typecasting operator.
What is typecasting?
Type casting refers to the conversion of one data type to another in a program. Typecasting can be done in two ways: automatically by the compiler and manually by the programmer or user.
Give it a try !!
Explanation/Steps
- Input the upper limit to print the Armstrong number from the user. Store it in some variable say end.
- Run a loop from 1 to end, increment 1 in each iteration. The loop structure should look like
for(i=1; i<=end; i++). - Inside the loop print current number i, if it is Armstrong number.
Solution
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int num, lastDigit, digits, sum, i, end;
/* Input upper limit from user */
/* Input number from user */
cout << "Enter the number : ";
cin >> end;
cout << "Armstrong number between 1 to entered number are: \n";
for( i = 1; i <= end; i++)
{
sum = 0;
/* Copy the value of num for processing */
num = i;
/* Find total digits in num */
digits = (int) log10(num) + 1;
/* Calculate sum of power of digits */
while(num > 0)
{
/* Extract last digit */
lastDigit = num % 10;
// Find sum of power of digits
sum = sum + pow(lastDigit, digits);
/* Remove the last digit */
num = num / 10;
}
/* Check for Armstrong number */
if(i == sum)
{
cout << i <<" ";
}
}
return 0;
}How was this exercise? Did you enjoy doing it?? I am assuming a positive response. (Am I very optimistic XD 😅)
I think now you must be comfortable with the loop problems. I guess now we are also able to find the pattern and similarities between different problems which is a very good thing.
"Remember Practice leads to Perfection".
Happy Learning !! 😀See you in the next article with more interesting concepts.