Python3 Program to Check if all array elements can be converted to pronic numbers by rotating digits
Given an array arr[] of size N, the task is to check if it is possible to convert all of the array elements to a pronic number by rotating the digits of array elements any number of times.
Examples:
Input: {321, 402, 246, 299}
Output: True
Explanation:
arr[0] ? Right rotation once modifies arr[0] to 132 (= 11 × 12).
arr[1] ? Right rotation once modifies arr[0] to 240 (= 15 × 16).
arr[2] ? Right rotation twice modifies arr[2] to 462 (= 21 × 22).
arr[3] ? Right rotation twice modifies arr[3] to 992 (= 31 × 32).Input: {433, 653, 402, 186}
Output: False
Approach: Follow the steps below to solve the problem:
- Traverse the array and check for each array element, whether it is possible to convert it to a pronic number.
- For each array element, apply all the possible rotations and check after each rotation, whether the generated number is pronic or not.
- If it is not possible to convert any array element to a pronic number, print “False”.
- Otherwise, print “True”.
Below is the implementation of the above approach:
Python3
# Python implementation of # the above approach # Function to check if a number # is a pronic number or not def isPronic(n): for i in range ( int (n * * ( 1 / 2 )) + 1 ): if i * (i + 1 ) = = n: return True return False # Function to check if any permutation # of n is a pronic number or not def checkRot(n): temp = str (n) for i in range ( len (temp)): if isPronic( int (temp)): return True temp = temp[ 1 :] + temp[ 0 ] return False # Function to check if all array # elements can be converted to # a pronic number or not def check(arr): # Traverse the array for i in arr: # If current element # cannot be converted # to a pronic number if not checkRot(i): return False return True # Driver Code arr = [ 321 , 402 , 246 , 299 ] print (check(arr)) |
True
Time Complexity: O(N3/2)
Auxiliary Space: O(1)
Please refer complete article on Check if all array elements can be converted to pronic numbers by rotating digits for more details!
Contact Us