Number of palindrome selfies-C++-php.cn

Number of palindrome selfies

A number is considered a "selfie number" if it can be represented using only its own digits and some mathematical operations.

For example, 936 is a selfie number.

$$\mathrm{936\:=\:(\sqrt{9})!^{3}\: \:6!\:=\:216\: \:720\:=\:No.936 chapter

You can see here that a series of operations are performed on the original number, and the result is equal to the original number.

The palindrome selfie number is a special selfie number. They satisfy the selfie multiplication rule.

Consider a number x.
Suppose the numerically reversed number of x is $\mathrm{x^\prime}$.
Let y be a number composed of the digits of x in different orders.
Suppose the number after the digital inversion of y is $\mathrm{y^\prime}$.

The number of palindromic selfies satisfies the following equation -

$$\mathrm{x\:×\:x^\prime\:=\:y\:×\:y^\prime}$$

Problem Statement

For a given number x, find its palindrome selfie number according to the selfie multiplication rule.

Example

Input: 1224
Output: 2142

Copy after login

illustrate -

Given x = 1224

So $\mathrm{x^\prime}$ = 4221 is obtained by reversing the number of x

Let y = 2142. y is formed using the digits of x in a different order

So $\mathrm{y^\prime}$ = 2412 is obtained by reversing the number of y

$\mathrm{x\:×\:x^\prime}$ = 1224 × 4221 = 5166504 and $\mathrm{y\:×\:y^\prime}$ = 2142 × 2412 = 5166504

Sincex× x' = y × y', y is the number of palindrome selfies of x.

Input 4669:
Output: 6496

Copy after login

illustrate -

Given x = 4669

So $\mathrm{x^\prime}$ = 9664 is obtained by reversing the number of x

Let y = 6496. y is formed using the digits of x in a different order

So $\mathrm{y^\prime}$ = 6946 is obtained by reversing the number of y

$\mathrm{x\:×\:x^\prime}$ = 4669 × 9664 = 45121216 and $\mathrm{y\:×\:y^\prime}$ = 6496× 6946= 45121216

Since x× x' = y × y', y is the palindrome selfie number of x.

Input: 456
Output: No palindromic selfie number exists

Copy after login

illustrate -

Given x = 456

So $\mathrm{x^\prime}$ = 654 is obtained by reversing the number of x

Let y = 546. y is formed using the digits of x in a different order

So $\mathrm{y^\prime}$ = 645 is obtained by reversing the number of y

$\mathrm{x\:×\:x^\prime}$ = 456 × 654 = 298224 and $\mathrm{y\:×\:y^\prime}$ = 546× 645= 352170

Since $\mathrm{x\:×\:x^\prime}$ ≠ $\mathrm{y\:×\:y^\prime}$, y is not the number of palindromic selfies of x.

No other permutation of 456 also satisfies the selfie multiplication rule.

solution

The solution to find the palindrome selfie number of a given number is quite intuitive and easy to understand.

The method includes the following steps -

Define a "reverse" function

Accepts an integer as input
Convert it to a string
Reverse string
Convert it back to an integer.

Define a function "Swap"

Taking integers i and j as input
Convert integer to string
Exchange the i-th and j-th characters in the string
Convert string back to integer.

Define a function "displacement"

Takes as input an integer, l, r, and a set of "permutations".
It recursively generates all possible permutations of integer numbers
It stores them in the "permutations" set.

Define a function "palindromic_selfie"

Takes an integer "num" and a set of "permutations" as input.
It uses the "permute" function to generate all possible permutations of the integer "num"
It then checks whether any of these permutations satisfy the palindromic selfie property by comparing the product of the number and its reverse order with the product of the permutation and its reverse order.
If such a permutation is found, the number is returned. Otherwise, -1 is returned.

In the main function, set a number "n" and an empty set to store the permutation.
Call the "palindromic_selfie" function with "n" and the empty set, and store the return result.
If the return result is -1, print "There is no palindrome selfie number". Otherwise, print the returned result.

Example: C program

The following C program finds the palindrome selfie number of a given integer (if one exists) and returns it. It does this by using the permute() function to find all possible permutations of a given number, and then using the reverse() function to determine whether the given number and any permutations of that number satisfy the selfie multiplication rules in the palindrome_selfie() function. If no such number exists, "No Palindrome Selfie Number Exists" is printed.

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

// Function to reverse the digits of a number
int reverse(int num){
   
   // converting number to string
   string str = to_string(num);
   reverse(str.begin(), str.end());
   
   // converting string to integer
   num = stoi(str);
   return num;
}

// Function that Swaps the digits i and j in the num
int Swap(int num, int i, int j){
   char temp;
   
   // converting number to string
   string s = to_string(num);
   
   // Swap the ith and jth character
   temp = s[i];
   s[i] = s[j];
   s[j] = temp;
   
   // Convert the string back to int and return
   return stoi(s);
}

// Function to get all possible permutations of the digits in num
void permute(int num, int l, int r, set<int> &permutations){
   
   // Adds the new permutation obtained in the set
   if (l == r)
      permutations.insert(num);
   else{
      for (int i = l; i <= r; i++){
         
         // Swap digits to get a different ordering
         int num_copy = Swap(num, l, i);
         
         // Recurse to next pair of digits
         permute(num_copy, l + 1, r, permutations);
      }
   }
}

// Function to check for palindrome selfie number
int palindromic_selfie(int num, set<int>& permutations) {
   
   // Length of the number required for calculating all permutations of the digits
   int l = to_string(num).length() - 1;
   permute(num, 0, l, permutations); // Calculate all permutations
   
   //Remove the number and its reverse from the obtained set as this is the LHS of multiplicative equation
   auto n1 = permutations.find(reverse(num));
   auto n2 = permutations.find(num);
   if (n1 != permutations.end())
      permutations.erase(n1);
   if (n2 != permutations.end())
      permutations.erase(n2);
   
   // Go through all other permutations of the number
   for (set<int>::iterator it = permutations.begin(); it != permutations.end(); it++) {
      int num2 = *it;
      
      // Check if selfie multiplicative rule holds i.e. x * reverse(x) = y * reverse(y)
      if (num * reverse(num) == num2 * reverse(num2)) {
         return num2;
      }
   }
   
   // If no such number found
   return -1;
}
int main(){
   int n = 1234;
   cout << "n: " << n << endl;
   set<int> permutations;
   int ans = palindromic_selfie(n, permutations);
   if (ans == -1) {
      cout << "No Palindromic Selfie Number Exists" << endl;
   }
   else{
      cout << ans << endl;
   }
   return 0;
}

Copy after login

输出

n: 1234
No Palindromic Selfie Number Exists

Copy after login

时间和空间复杂度分析

时间复杂度：O(n!)

此代码的时间复杂度为 O(n!)，其中 n 是输入数字的位数。这是因为有 n! n 位数字的排列，并且 permute() 方法生成数字的所有潜在排列。

空间复杂度：O(n!)

由于集合“排列”包含所有可能的数字组合，等于 n!，因此该代码的空间复杂度为 O(n!)。 verse() 和 Swap() 函数的空间复杂度为 O(n)，因为它们还生成长度为 n 的临时字符串。空间复杂度为 O(n!) 的排列集合主导了整个代码的空间复杂度。

结论

Number of palindrome selfies是数学中一个有趣的概念。它们满足自拍乘法方程。本文讨论了一种方法来查找一个数字是否具有回文自拍号码，如果是，则返回它。对问题的概念、解决方法、C++程序以及程序的时间和空间复杂度进行了深入分析。

The above is the detailed content of Number of palindrome selfies. For more information, please follow other related articles on the PHP Chinese website!