Sponsored
Sponsored
The simplest way to solve this problem is to iterate over each pair of integers from arr1 and arr2. For each pair, convert the integers to strings and compare character by character to find the common prefix. Keep a running maximum of the lengths of these prefixes.
Since we are comparing each pair, the time complexity is O(n * m * k), where n is the length of arr1, m is the length of arr2, and k is the length of the longest number when converted to a string. Space complexity is O(1) as we're only storing a few additional variables.
Time complexity: O(n * m * k), Space complexity: O(1)
1using System;
2
3class Program {
4 public static int CommonPrefixLength(string a, string b) {
5 int i = 0;
6 while (i < a.Length && i < b.Length && a[i] == b[i]) {
7 i++;
8 }
9 return i;
10 }
11
12 public static int LongestCommonPrefix(int[] arr1, int[] arr2) {
13 int maxLength = 0;
14 foreach(var num1 in arr1) {
15 foreach(var num2 in arr2) {
16 string str1 = num1.ToString();
17 string str2 = num2.ToString();
18 int currLength = CommonPrefixLength(str1, str2);
19 maxLength = Math.Max(maxLength, currLength);
20 }
21 }
22 return maxLength;
23 }
24
25 static void Main() {
26 int[] arr1 = {1, 10, 100};
27 int[] arr2 = {1000};
28 Console.WriteLine(LongestCommonPrefix(arr1, arr2));
29 }
30}
31The C# solution involves iterating over pairs of integers from arr1 and arr2. It calculates the common prefix length using character comparison and stores the maximum length found for any pair.
This optimized approach leverages sorting of the input arrays to reduce comparisons. After sorting, only consecutive elements can potentially have a longer common prefix with elements of the other array than already found max. This minimizes the number of comparisons, improving efficiency over the brute force approach.
Time complexity may approach O(n + m) in the best-case scenario where common prefixes are found early, but in the worst case it remains approximately O(n * m). The space complexity is still O(1).
Average Time complexity: O(n log n + m log m + n + m), Space complexity: O(1)
#include <string>
#include <algorithm>
using namespace std;
int commonPrefixLength(const string& a, const string& b) {
int length = 0;
while (length < a.size() && length < b.size() && a[length] == b[length]) {
length++;
}
return length;
}
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
sort(arr1.begin(), arr1.end());
sort(arr2.begin(), arr2.end());
int maxLength = 0;
for (const int& num1 : arr1) {
for (const int& num2 : arr2) {
maxLength = max(maxLength, commonPrefixLength(to_string(num1), to_string(num2)));
}
}
return maxLength;
}
int main() {
vector<int> arr1 = {1, 10, 100};
vector<int> arr2 = {1000};
cout << longestCommonPrefix(arr1, arr2) << endl;
return 0;
}The C++ code improves efficiency by sorting both arrays. The common prefix checks are optimized by focusing primarily on consecutive elements of sorted arrays, minimizing unnecessary comparisons.