Given an array A[] of N numbers, the task is to find the length of the longest valid number that can be formed by connecting one or more numbers from the array such that, while connecting two numbers the last digit of the previous number is the same as the first digit of the next number.
Examples:
Input: A = [100, 234, 416, 654, 412, 298, 820, 177]
Output: 12
Explanation: The valid numbers are 234416654(connecting a1, a2, a3) and 234416654412 connecting a[1], a[2], a[3], a[4]. The longest valid number is 234416654412, which has a length of 12.Input: A = [81, 24, 478, 905, 331, 138, 721, 565]
Output: 5
Explanation: The valid numbers are 81138(connecting a0, a4), and 565(a7). Maximum length is 5.
Approach: This can be solved with the following idea:
The approach is to use dynamic programming to find the length of the longest valid number that can be formed by connecting one or more numbers from the given array. The approach uses a 2D array dp to store previously computed results, where dp[i][j] represents the length of the longest valid number that ends with the digit i and starts with the digit j. The algorithm iterates through the array in reverse order and for each number, it computes the length of the longest valid number that can be formed by connecting the number to a previously processed number. The computed results are stored in a temporary array v. Finally, the algorithm updates the dp array with the computed results and finds the maximum valid length. The time complexity of this algorithm is O(n^2), where n is the length of the array.
Below are the steps involved in the implementation of the code:
- Create a 2D array of size 10×10 named ‘dp‘ to store previously computed results.
- Iterate through the array ‘arr‘ in reverse order, starting from the last element and moving toward the first element.
- For each element of ‘arr’, convert it to a string ‘numString‘, and get its last digit ‘lastDigit‘.
- Create a temporary array ‘v’ of size 10 to store the results for each digit ‘d’.
- For each digit ‘d’ from 0 to 9, if there is a previously computed result for the pair of digits ‘lastDigit’ and ‘d’ in the ‘dp’ array, update ‘v[d]’ to be the sum of the length of ‘numString’ and the previously computed result.
- Update ‘v[lastDigit]’ to be the maximum between its current value and the length of ‘numString’.
- Get the first digit ‘firstDigit‘ of ‘numString‘.
- For each digit ‘d’ from 0 to 9, update the value in ‘dp[firstDigit][d]’ to be the maximum between its current value and ‘v[d]’.
- Update the maximum valid length ‘maxValidLength’ to be the maximum between its current value and ‘dp[firstDigit][firstDigit]’.
- Return ‘maxValidLength‘.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <algorithm>#include <iostream>#include <string>using namespace std;int findLongestValidNumberLength(int arr[], int size){ int maxValidLength = 0; // Create a 2D array to store previous results int dp[10][10] = { 0 }; // Iterate through the array in reverse order for (int i = size - 1; i >= 0; --i) { // Convert the number to a string string numString = to_string(arr[i]); // Get the last digit of the number int lastDigit = numString.back() - '0'; // Create a temporary array to store the results int v[10] = { 0 }; for (int d = 0; d < 10; ++d) { // If there is a previously computed result for // the last digit and the current digit, update // the temporary array if (dp[lastDigit][d] > 0) { v[d] = numString.length() + dp[lastDigit][d]; } } // Update the temporary array to include the current // number v[lastDigit] = max(v[lastDigit], static_cast<int>(numString.length())); // Get the first digit of the number int firstDigit = numString.front() - '0'; for (int d = 0; d < 10; ++d) { // Update the 2D array with the computed results dp[firstDigit][d] = max(dp[firstDigit][d], v[d]); } // Update the maximum valid length if necessary maxValidLength = max(maxValidLength, dp[firstDigit][firstDigit]); } return maxValidLength;}// Driver codeint main(){ // Sample inputs int arr1[] = { 100, 234, 416, 654, 412, 298, 820, 177 }; int size1 = sizeof(arr1) / sizeof(arr1[0]); int arr2[] = { 81, 24, 478, 905, 331, 138, 721, 565 }; int size2 = sizeof(arr2) / sizeof(arr2[0]); int arr3[] = { 1111, 2222, 3333, 4444, 5555 }; int size3 = sizeof(arr3) / sizeof(arr3[0]); // Function calls cout << findLongestValidNumberLength(arr1, size1) << endl; cout << findLongestValidNumberLength(arr2, size2) << endl; cout << findLongestValidNumberLength(arr3, size3) << endl; return 0;}// This code is contributed by akshitaguprzj3 |
Java
// Java code for the above approach:class GFG { public static int findLongestValidNumberLength(int[] arr) { int maxValidLength = 0; // Create a 2D array to store // previous results int[][] dp = new int[10][10]; // Iterate through the array in // reverse order for (int i = arr.length - 1; i >= 0; --i) { // Convert the number // to a string String numString = String.valueOf(arr[i]); // Get the last digit // of the number int lastDigit = numString.charAt(numString.length() - 1) - '0'; // Create a temporary array // to store the results int[] v = new int[10]; for (int d = 0; d < 10; ++d) { // If there is a previously // computed result for the // last digit and the current // digit, update the // temporary array if (dp[lastDigit][d] > 0) { v[d] = numString.length() + dp[lastDigit][d]; } } // Update the temporary array // to include the current // number v[lastDigit] = Math.max(v[lastDigit], numString.length()); // Get the first digit // of the number int firstDigit = numString.charAt(0) - '0'; for (int d = 0; d < 10; ++d) { // Update the 2D array with // the computed results dp[firstDigit][d] = Math.max(dp[firstDigit][d], v[d]); } // Update the maximum valid // length if necessary maxValidLength = Math.max( maxValidLength, dp[firstDigit][firstDigit]); } return maxValidLength; } // Driver code public static void main(String[] args) { // Sample inputs int[] arr1 = { 100, 234, 416, 654, 412, 298, 820, 177 }; int[] arr2 = { 81, 24, 478, 905, 331, 138, 721, 565 }; int[] arr3 = { 1111, 2222, 3333, 4444, 5555 }; // Function call System.out.println( findLongestValidNumberLength(arr1)); System.out.println( findLongestValidNumberLength(arr2)); System.out.println( findLongestValidNumberLength(arr3)); }} |
Python3
# Python3 code for the above approach:def findLongestValidNumberLength(arr): size = len(arr) maxValidLength = 0 # Create a 2D list to store previous results dp = [[0] * 10 for _ in range(10)] # Iterate through the list in reverse order for i in range(size - 1, -1, -1): # Convert the number to a string numString = str(arr[i]) # Get the last digit of the number lastDigit = int(numString[-1]) # Create a temporary list to store the results v = [0] * 10 for d in range(10): # If there is a previously computed result for # the last digit and the current digit, update # the temporary list if dp[lastDigit][d] > 0: v[d] = len(numString) + dp[lastDigit][d] # Update the temporary list to include the current # number v[lastDigit] = max(v[lastDigit], len(numString)) # Get the first digit of the number firstDigit = int(numString[0]) for d in range(10): # Update the 2D list with the computed results dp[firstDigit][d] = max(dp[firstDigit][d], v[d]) # Update the maximum valid length if necessary maxValidLength = max(maxValidLength, dp[firstDigit][firstDigit]) return maxValidLength# Driver codearr1 = [100, 234, 416, 654, 412, 298, 820, 177]arr2 = [81, 24, 478, 905, 331, 138, 721, 565]arr3 = [1111, 2222, 3333, 4444, 5555]# Function callsprint(findLongestValidNumberLength(arr1))print(findLongestValidNumberLength(arr2))print(findLongestValidNumberLength(arr3))# This code is contributed by rambabuguphka |
C#
using System;class Program { static void Main(string[] args) { int[] arr1 = { 100, 234, 416, 654, 412, 298, 820, 177 }; int[] arr2 = { 81, 24, 478, 905, 331, 138, 721, 565 }; int[] arr3 = { 1111, 2222, 3333, 4444, 5555 }; Console.WriteLine( findLongestValidNumberLength(arr1)); Console.WriteLine( findLongestValidNumberLength(arr2)); Console.WriteLine( findLongestValidNumberLength(arr3)); Console.ReadKey(); } public static int findLongestValidNumberLength(int[] arr) { int maxValidLength = 0; // Create a 2D array to store // previous results int[, ] dp = new int[10, 10]; // Iterate through the array in // reverse order for (int i = arr.Length - 1; i >= 0; --i) { // Convert the number // to a string string numString = arr[i].ToString(); // Get the last digit // of the number int lastDigit = numString[numString.Length - 1] - '0'; // Create a temporary array // to store the results int[] v = new int[10]; for (int d = 0; d < 10; ++d) { // If there is a previously // computed result for the // last digit and the current // digit, update the // temporary array if (dp[lastDigit, d] > 0) { v[d] = numString.Length + dp[lastDigit, d]; } } // Update the temporary array // to include the current // number v[lastDigit] = Math.Max(v[lastDigit], numString.Length); // Get the first digit // of the number int firstDigit = numString[0] - '0'; for (int d = 0; d < 10; ++d) { // Update the 2D array with // the computed results dp[firstDigit, d] = Math.Max(dp[firstDigit, d], v[d]); } // Update the maximum valid // length if necessary maxValidLength = Math.Max( maxValidLength, dp[firstDigit, firstDigit]); } return maxValidLength; }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
// JavaScript code for the above approach:function findLongestValidNumberLength(arr) { let size = arr.length; let maxValidLength = 0; // Create a 2D array to store previous results let dp = new Array(10); for (let i = 0; i < 10; i++) { dp[i] = new Array(10).fill(0); } // Iterate through the array in reverse order for (let i = size - 1; i >= 0; i--) { // Convert the number to a string let numString = String(arr[i]); // Get the last digit of the number let lastDigit = parseInt(numString[numString.length - 1]); // Create a temporary array to store the results let v = new Array(10).fill(0); for (let d = 0; d < 10; d++) { // If there is a previously computed result for // the last digit and the current digit, update // the temporary array if (dp[lastDigit][d] > 0) { v[d] = numString.length + dp[lastDigit][d]; } } // Update the temporary array to include the current // number v[lastDigit] = Math.max(v[lastDigit], numString.length); // Get the first digit of the number let firstDigit = parseInt(numString[0]); for (let d = 0; d < 10; d++) { // Update the 2D array with the computed results dp[firstDigit][d] = Math.max(dp[firstDigit][d], v[d]); } // Update the maximum valid length if necessary maxValidLength = Math.max(maxValidLength, dp[firstDigit][firstDigit]); } return maxValidLength;}// Driver codelet arr1 = [100, 234, 416, 654, 412, 298, 820, 177];let arr2 = [81, 24, 478, 905, 331, 138, 721, 565];let arr3 = [1111, 2222, 3333, 4444, 5555];// Function callsconsole.log(findLongestValidNumberLength(arr1));console.log(findLongestValidNumberLength(arr2));console.log(findLongestValidNumberLength(arr3));// This code is contributed by Tapesh(tapeshdua420) |
Output
12 5 4
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
