The time complexity of the linear search problem is meant to the complexity of time to make the program run. The time complexity in linear search will be clear with an example, which has been given in below. In this problem, a linear search with the condition has been applied to print the multiplier of a number and find the optimal solution for this problem.
Problem:
Q. 1: Find the multiplier of a number X in a range N. Consider optimal solution for the problem.
or
Q. 2: Find the multiplier of a number with an optimal solution.
Inputs Details: The first input of the program will be an integer T, which indicates the number of test cases. In the next T number of lines, you have to take input of the integers X and N twice.
Output Details: The output of the program has to print the multiplier of X from X to N. If the value of X is greater than N then invalid will print.
Solution of the problem:
The input part of the problem states that the number of test cases must be taken first. Then first take the T-test case. Test cases are always of the integer data type. Then we can write for the test case.
int T;
scanf("%d", &T);
Then we have to take two integers X and N inputs. Here we will work with the integer data type. So, let us write the integers X and N for input.
int X, N;
scanf("%d %d", &X, &N);
Since we will print integers within a range, we need to declare a few additional variables for the loop. For that, we can take two variables of integer data type.
int i, j;
Then variables of the program can be declared as:
int T;
int X, N, i, j;
First let's take a loop, which will run as many times as the value of T to take the X and N input. Now let's write.
for (i=0; i<T; i++) { }
Now, we have to take the value input of X and N every time in the loop.
for (i=0; i<T; i++)
{
scanf("%d %d", &X, &N);
}
After taking the input of X and N. Now, the program needs to verify whether is valid or invalid to print multipliers of X. If X is better than N, then the program will print invalid.
if (X>N)
{
printf("Invalid\n");
}
Now the original condition 'invalid' has to be considered in this code. If the invalid condition is not true, then the loop will run from 1 to N, and we will find the multiplier of X in the loop. The product of X is the number that is divisible by X. Then let's write.
for(j=1; j<=N; j++)
{
if(j%X==0)
{
printf("%d\n", j);
}
}
Ok. Our program is ready and the full program is here:
#include<stdio.h>
int main()
{
int T;
int X, N, i, j;
scanf("%d", &T);
for (i=0; i<T; i++)
{
scanf("%d %d", &X, &N);
if (X>N)
{
printf("Invalid\n");
}
for(j=1; j<=N; j++)
{
if(j%X==0)
{
printf("%d\n", j);
}
}
}
return 0;
}
Now, we have to think about whether the program is optimal or not. Here the loop will run from 1 to N. If the value of N is 100,000,000, then the loop will run 100,000,000 times, which is time costly. So, this program is not the optimal solution. So, need to think again. Each time we have to calculate whether the integer is a multiplier of X. Suppose, if we start with the value of X instead of 1 and increase it exactly one by one without increasing it one step at a time, then many iterations will decrease. With that, you don't have to use the 'if'. This is because the value of X is equal to the value that is being multiplied so that its value is always a multiplier of X. Then the loop will be like this.
for(j=X; j<=N; j+=X)
{
if(j%X==0)
{
printf("%d\n", j);
}
}
Finally, the program is optimal. This process is called Runtime Reduction or Optimization. Both solutions work the same, but the program of the next optimal solution runs faster than the first. Now let's write the whole program like this:
#include<stdio.h>
int main()
{
int T;
int X, N, i, j;
scanf("%d", &T);
for (i=0; i<T; i++)
{
scanf("%d %d", &X, &N);
if (X>N)
{
printf("Invalid\n");
}
for(j=X; j<=N; j+=X)
{
if(j%X==0)
{
printf("%d\n", j);
}
}
}
return 0;
}
Sample Input:
4
2 10
99 1000
200 60
4444 44
Sample Output:
2
4
6
8
10
99
198
297
396
495
594
693
792
891
990
Invalid
Invalid
Read Similar Posts:
3. Insertion Sort Time Complexity