Check if Array elements can be made equal by adding unit digit to the number
Given an array arr[] of N integers, the task is to check whether it is possible to make all the array elements identical by applying the following option any number of times:
- Choose any number and add its unit digit to it.
Examples:
Input: arr[] = {1, 2, 4, 8, 24}
Output: Possible
Explanation:
For 1: 1 -> 2 -> 4 -> 8 -> 16- > 22 -> 24
For 2: 2 -> 4 -> 8 -> 16 -> 22 -> 24
For 4: 4 -> 8 -> 16 -> 22 -> 24
For 8: 16- > 22 -> 24
For 24: 24 (it’s already 24, so, no need to change)Input: arr[] = {5, 10}
Output: Possible
Approach: The problem can be solved based on the following observation.
Any number can be converted to have either 0 or 2 as its unit digit by repetitively adding its unit digit to itself at most 10 times.
The idea is to
- Initially make the unit digit of every number either 2 or 0.
- Then for the numbers that have 0 as their unit digit, all of those numbers must be same(because x+0 = 0), and
- For every number with 2 as the unit digit, the difference between them must be multiple of 20 so that they can be made equal.
Follow the steps to solve this problem:
- Add the unit digit of each number to itself until its unit digit becomes 2 or 0.
- For every number that has 0 as a unit digit, check whether all the numbers are equal.
- For numbers with 2 as the unit digit, the difference between them must be a multiple of 20.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to check whether the elements // of array can be equal or not string solve( int * arr, int n) { // Initialize flag as 1 bool flag = 1; // Make unit digit of every element of array // with either 0 or 2 for ( int i = 0; i < n; i++) { while (arr[i] % 10 != 0 && arr[i] % 10 != 2) arr[i] += arr[i] % 10; } // Check if it is possible to make // the array elements identical or not for ( int i = 0; i < n; i++) { // Elements for 0 as unit digit if ((arr[0] % 10 == 0) && (arr[i] != arr[0])) { flag = 0; break ; } // Elements for 2 as unit digit if ((arr[i] - arr[0]) % 20) { flag = 0; break ; } } if (flag) return "Possible" ; else return "Impossible" ; } // Driver Code int main() { int arr[] = { 1, 2, 4, 8, 24 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call cout << solve(arr, N); return 0; } |
Java
// Java code for the above approach import java.io.*; class GFG { // Function to check whether the elements // of array can be equal or not static String solve( int [] arr, int n) { // Initialize flag as 1 boolean flag = true ; // Make unit digit of every element of array // with either 0 or 2 for ( int i = 0 ; i < n; i++) { while (arr[i] % 10 != 0 && arr[i] % 10 != 2 ) arr[i] += arr[i] % 10 ; } // Check if it is possible to make // the array elements identical or not for ( int i = 0 ; i < n; i++) { // Elements for 0 as unit digit if ((arr[ 0 ] % 10 == 0 ) && (arr[i] != arr[ 0 ])) { flag = false ; break ; } // Elements for 2 as unit digit if (((arr[i] - arr[ 0 ]) % 20 ) != 0 ) { flag = false ; break ; } } if (flag ) return "Possible" ; else return "Impossible" ; } // Driver code public static void main(String[] args) { int arr[] = { 1 , 2 , 4 , 8 , 24 }; int N = arr.length; // Function call System.out.println( solve(arr, N)); } } // This code is contributed by sanjoy_62. |
Python3
# Python3 code for the above approach # Function to check whether the elements of array can # be equal or not def solve(arr, n): # Initialize flag as true flag = True # Make unit digit of every element of array with # either 0 or 2 # for (int i = 0; i < n; i++) { for i in range ( 0 , n): while ((arr[i] % 10 ! = 0 ) and (arr[i] % 10 ! = 2 )): arr[i] + = arr[i] % 10 # Check if it is possible to make the array # elements identical or not # for (int i = 0; i < n; i++) { for i in range ( 0 , n): # Elements for 0 as unit digit if ((arr[ 0 ] % 10 ) = = 0 and (arr[i] ! = arr[ 0 ])): flag = False break # Elements for 2 as unit digit if ((arr[i] - arr[ 0 ]) % 20 ! = 0 ): flag = False break if (flag): return "Possible" else : return "Impossible" # Driver Code arr = [ 1 , 2 , 4 , 8 , 24 ] N = len (arr) # Function call ans = solve(arr, N) print (ans) # This code is contributed by akashish. |
C#
// C# code for the above approach using System; public class GFG { // Function to check whether the elements of array can // be equal or not static string solve( int [] arr, int n) { // Initialize flag as true bool flag = true ; // Make unit digit of every element of array with // either 0 or 2 for ( int i = 0; i < n; i++) { while (arr[i] % 10 != 0 && arr[i] % 10 != 2) { arr[i] += arr[i] % 10; } } // Check if it is possible to make the array // elements identical or not for ( int i = 0; i < n; i++) { // Elements for 0 as unit digit if ((arr[0] % 10) == 0 && (arr[i] != arr[0])) { flag = false ; break ; } // Elements for 2 as unit digit if ((arr[i] - arr[0]) % 20 != 0) { flag = false ; break ; } } if (flag) return "Possible" ; else return "Impossible" ; } static public void Main() { // Code int [] arr = { 1, 2, 4, 8, 24 }; int N = arr.Length; // Function call Console.Write(solve(arr, N)); } } // This code is contributed by lokeshmvs21. |
Javascript
<script> // JavaScript code for the approach // Function to check whether the elements // of array can be equal or not function solve(arr, n) { // Initialize flag as 1 let flag = true ; // Make unit digit of every element of array // with either 0 or 2 for (let i = 0; i < n; i++) { while (arr[i] % 10 != 0 && arr[i] % 10 != 2) arr[i] += arr[i] % 10; } // Check if it is possible to make // the array elements identical or not for (let i = 0; i < n; i++) { // Elements for 0 as unit digit if ((arr[0] % 10 == 0) && (arr[i] != arr[0])) { flag = false ; break ; } // Elements for 2 as unit digit if (((arr[i] - arr[0]) % 20) != 0) { flag = false ; break ; } } if (flag ) return "Possible" ; else return "Impossible" ; } // Driver code // Given input let arr = [ 1, 2, 4, 8, 24 ]; let N = arr.length; // Function call document.write( solve(arr, N)); // This code is contributed by code_hunt. </script> |
Possible
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us