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:
Java
// Java program for the above approach import java.io.*;import java.lang.*;import java.util.*; class GFG { // function to check Pronic Number static boolean isPronic(int x) { for (int i = 0; i < (int)(Math.sqrt(x)) + 1; i++) { // Checking Pronic Number // by multiplying consecutive // numbers if (x == i * (i + 1)) { return true; } } return false; } // Function to check if any permutation // of val is a pronic number or not static boolean checkRot(int val) { String temp = Integer.toString(val); for (int i = 0; i < temp.length(); i++) { if (isPronic(Integer.parseInt(temp)) == true) { return true; } temp = temp.substring(1) + temp.charAt(0); } return false; } // Function to check if all array // elements can be converted to // a pronic number or not static boolean check(int arr[], int N) { // Traverse the array for (int i = 0; i < N; i++) { // If current element // cannot be converted // to a pronic number if (checkRot(arr[i]) == false) { return false; } } return true; } // Driver code public static void main(String[] args) { // Given array int arr[] = { 321, 402, 246, 299 }; int N = arr.length; // Function call System.out.println( (check(arr, N) ? "True" : "False")); }} // This code is contributed by Kingash. |
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!
