What is the position of n in the number composed of 2, 3, 5, and 7?

The problem statement consists of printing the position of n in a number consisting of 2, 3, 5 and 7, where n can be any positive number given by the user.

A number consisting of 2, 3, 5 and 7 means that this will be a strictly increasing sequence of numbers containing only the numbers 2, 3, 5 or 7, the first four prime numbers. The first few numbers of the sequence where all the numbers are only 2,3,5 and 7 because their numbers are 2, 3, 5, 7, 22, 23, 25, 27, 32, 33, 35, 37, etc.

Basically, each number in the sequence is a combination of these 4 numbers (i.e. 2, 3, 5, or 7), and the sequence is arranged in ascending order.

In this question we will be given a number N whose digits are only 2, 3, 5 and 7, we need to find out the position of the given number in the sequence and print it, this will be required Digital output.

Let us understand this problem better with the following example.

INPUT : N=33</p><p>OUTPUT : 10

Explanation - The given number containing only 2, 3, 5 or 7 in the input is 33. In a number sequence with only the digits 2, 3, 5, or 7, the position of 33 is the 10th position. Therefore, our output is 10.

INPUT : 52</p><p>OUTPUT : 13

Explanation - The number in the input is 52. When we follow the pattern in the sequence, each number has 2, 3, 5 or 7 as its digit, and the sequence is strictly in increasing order, we find 52 at position 13. So our desired output is 13.

Let us understand the algorithm to directly find the position of a given number without creating the entire sequence.

algorithm

If we look at number sequences where the numbers are only 2, 3, 5 or 7, we will see that we can only form 4 combinations of numbers with a specific number. We will use this logic to figure out the position of any given number N.

The positions of the first four digits are as follows:

2: First place

3: Second place

5：Third place

7：Fourth place

Since the sequence is in ascending order, the next four numbers will be 2 digits with the first number being 2, since we can only form 4 numbers with specific numbers.

We can find the position of any number by multiplying the position of the first digit on the left by 4 and adding the position of that particular number.

For example, N=52

The initial position will be 0.

Starting from the number on the left, the position of 5 in the sequence will be position*4 position of 5, that is, 0*4 3=3. Position is now 3.

The next number is 2, so the position of the number will be 3*4 1, because the current position is 3 times 4, adding the position of the current number gives us position 13, that is, there are 52 positions in the sequence of numbers.

To solve this problem, we just initialize the position to 0. Then keep checking each number until the last digit of the number and update the position accordingly -

For the number 2, the position will be position*4 1.

For the number 3, the position will be position*4 2.

For the number 5, the position will be position*4 3.

For the number 7, the position will be position*4 4.

We update the position by multiplying by 4 because for each possible number we can only make 4 combinations. So each time we multiply the position by 4 and add the position of the current number, we get the position of the number N, which is only 2, 3, 5 or 7.

We will use this algorithm in our approach in order to solve the problem efficiently.

method

Steps to be followed when implementing the algorithm in our method to print the position of a number N consisting only of 2, 3, 5 or 7 -

• We will create a function to get the position of a given number which is only 2, 3, 5 or 7.

• We will get the input number N in the form of a string.

• So, from i=0 to i

• For the first case, if the i-th number is 2, we will multiply that position by 4 and 1, since 1 is the position of 2. Similarly, we will use the formula to calculate the position of the number up to i position based on the i-th digit discussed in the algorithm section.

• Each iteration, the position is continuously updated based on the current i-th number.

• When we finish iterating through the entire string, return the value stored at that location, which is the output we need.

Example

C code for this method:

#include <bits/stdc++.h>
using namespace std;

//to find the position of the number with only 2,3,5 or 7 as its digits
int position(string N){

   int p=0; //to store the position of the number

   //iterating in a for loop to calculate the position
   for(int i=0;i<N.size();i++){

      if(N[i]=='2'){ 
         //if the digit is 2
         p = p * 4 + 1; 
         //multiplying the position by 4 and adding the position of the digit
      }
      else if(N[i]=='3'){ 
         // if the digit is 3
         p = p * 4 + 2;
      }
      else if(N[i]=='5'){ 
         //if the digit is 5
         p = p * 4 + 3;
      }
      else{ // for the case when digit is 7
         p = p * 4 + 4;
      }
   }

   return p; //return the position of the number N

}
using namespace std;

int main() {
   string N;
   N = "2357";
   //calling the function
   cout<<"The position of "<<N<<" in the sequence is : "<<position(N)<<endl;

   N = "3327";
   cout<<"The position of "<<N<<" in the sequence is : "<<position(N)<<endl;

   return 0;
}

Output

The position of 2357 in the sequence is : 112
The position of 3327 in the sequence is : 168

Time complexity - O(n), where n is the length of the string or the number of digits in the number, since we iterate n times in the for loop to calculate the position in the given sequence number

Space Complexity - O(1) since we are not using any extra space to solve the problem.

in conclusion

This article discusses the algorithm to find the position of the number N in a sequence of numbers with the number 2, 3, 5 or 7, we have implemented this algorithm in our approach to solve the problem efficiently in O(n) time Using C without using any extra space.

I hope after reading this article you will be able to understand this problem and how to solve it in C.

The above is the detailed content of What is the position of n in the number composed of 2, 3, 5, and 7?. For more information, please follow other related articles on the PHP Chinese website!