# Count pairs in an array which have at least one digit common

Given an array of N numbers. Find out the number of pairs i and j such that i < j and Ai and Aj have atleast one digit common (For e.g. (11, 19) have 1 digit common but (36, 48) have no digit common)

Examples:

Input : A[] = { 10, 12, 24 }
Output : 2
Explanation: Two valid pairs are (10, 12) and (12, 24) which have atleast one digit common

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Method 1 (Brute Force) A naive approach to solve this problem is just by running two nested loops and consider all possible pairs. We can check if the two numbers have atleast one common digit, by extracting every digit of first number and try to find it in the extracted digits of second number. The task would become much easier we simply convert them into strings.

Below is the naive implementation.

## C++

 `// CPP Program to count pairs in an array ` `// with some common digit ` `#include ` ` `  `using` `namespace` `std; ` ` `  `// Returns true if the pair is valid, ` `// otherwise false ` `bool` `checkValidPair(``int` `num1, ``int` `num2) ` `{ ` `    ``// converting integers to strings ` `    ``string s1 = to_string(num1); ` `    ``string s2 = to_string(num2); ` ` `  `    ``// Iterate over the strings and check ` `    ``// if a character in first string is also ` `    ``// present in second string, return true ` `    ``for` `(``int` `i = 0; i < s1.size(); i++) ` `        ``for` `(``int` `j = 0; j < s2.size(); j++) ` `            ``if` `(s1[i] == s2[j]) ` `                ``return` `true``; ` ` `  `    ``// No common digit found ` `    ``return` `false``; ` `} ` ` `  `// Returns the number of valid pairs ` `int` `countPairs(``int` `arr[], ``int` `n) ` `{ ` `    ``int` `numberOfPairs = 0; ` ` `  `    ``// Iterate over all possible pairs ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``for` `(``int` `j = i + 1; j < n; j++) ` `            ``if` `(checkValidPair(arr[i], arr[j])) ` `                ``numberOfPairs++; ` ` `  `    ``return` `numberOfPairs; ` `} ` ` `  `// Driver Code to test above functions ` `int` `main() ` `{ ` `    ``int` `arr[] = { 10, 12, 24 }; ` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]); ` `    ``cout << countPairs(arr, n) << endl; ` `    ``return` `0; ` `} `

/div>

## Java

 `// Java Program to count  ` `// pairs in an array ` `// with some common digit ` `import` `java.io.*; ` ` `  `class` `GFG  ` `{ ` `     `  `    ``// Returns true if the pair  ` `    ``// is valid, otherwise false ` `    ``static` `boolean` `checkValidPair(``int` `num1,  ` `                                  ``int` `num2) ` `    ``{ ` `        ``// converting integers ` `        ``// to strings ` `        ``String s1 = Integer.toString(num1); ` `        ``String s2 = Integer.toString(num2); ` `     `  `        ``// Iterate over the strings  ` `        ``// and check if a character  ` `        ``// in first string is also ` `        ``// present in second string,  ` `        ``// return true ` `        ``for` `(``int` `i = ``0``; i < s1.length(); i++) ` `            ``for` `(``int` `j = ``0``; j < s2.length(); j++) ` `                ``if` `(s1.charAt(i) == s2.charAt(j)) ` `                    ``return` `true``; ` `     `  `        ``// No common  ` `        ``// digit found ` `        ``return` `false``; ` `    ``} ` `     `  `    ``// Returns the number ` `    ``// of valid pairs ` `    ``static` `int` `countPairs(``int` `[]arr, ``int` `n) ` `    ``{ ` `        ``int` `numberOfPairs = ``0``; ` `     `  `        ``// Iterate over all ` `        ``// possible pairs ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `            ``for` `(``int` `j = i + ``1``; j < n; j++) ` `                ``if` `(checkValidPair(arr[i], arr[j])) ` `                    ``numberOfPairs++; ` `     `  `        ``return` `numberOfPairs; ` `    ``} ` `     `  `    ``// Driver Code  ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `[]arr = ``new` `int``[]{ ``10``, ``12``, ``24` `}; ` `        ``int` `n = arr.length; ` `        ``System.out.print(countPairs(arr, n)); ` `    ``} ` `} ` ` `  `// This code is contributed  ` `// by manish shaw. `

## Python3

 `# Python3 Program to count pairs in  ` `# an array with some common digit  ` ` `  `# Returns true if the pair is  ` `# valid, otherwise false  ` `def` `checkValidPair(num1, num2) : ` `     `  `    ``# converting integers to strings  ` `    ``s1 ``=` `str``(num1) ` `    ``s2 ``=` `str``(num2)  ` ` `  `    ``# Iterate over the strings and check if ` `    ``# a character in first string is also  ` `    ``# present in second string, return true  ` `    ``for` `i ``in` `range``(``len``(s1)) :  ` `        ``for` `j ``in` `range``(``len``(s2)) :  ` `            ``if` `(s1[i] ``=``=` `s2[j]) : ` `                ``return` `True``;  ` ` `  `    ``# No common digit found  ` `    ``return` `False``;  ` ` `  `# Returns the number of valid pairs  ` `def` `countPairs(arr, n) : ` `     `  `    ``numberOfPairs ``=` `0` ` `  `    ``# Iterate over all possible pairs  ` `    ``for` `i ``in` `range``(n) : ` `        ``for` `j ``in` `range``(i ``+` `1``, n) : ` `            ``if` `(checkValidPair(arr[i], arr[j])) : ` `                ``numberOfPairs ``+``=` `1` ` `  `    ``return` `numberOfPairs ` ` `  `# Driver Code  ` `if` `__name__ ``=``=` `"__main__"` `:  ` `    ``arr ``=` `[ ``10``, ``12``, ``24` `] ` `    ``n ``=` `len``(arr) ` `    ``print``(countPairs(arr, n)) ` ` `  `# This code is contributed by Ryuga `

## C#

 `// C# Program to count pairs in an array ` `// with some common digit ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// Returns true if the pair is valid, ` `    ``// otherwise false ` `    ``static` `bool` `checkValidPair(``int` `num1, ``int` `num2) ` `    ``{ ` `        ``// converting integers to strings ` `        ``string` `s1 = num1.ToString(); ` `        ``string` `s2 = num2.ToString(); ` `     `  `        ``// Iterate over the strings and check ` `        ``// if a character in first string is also ` `        ``// present in second string, return true ` `        ``for` `(``int` `i = 0; i < s1.Length; i++) ` `            ``for` `(``int` `j = 0; j < s2.Length; j++) ` `                ``if` `(s1[i] == s2[j]) ` `                    ``return` `true``; ` `     `  `        ``// No common digit found ` `        ``return` `false``; ` `    ``} ` `     `  `    ``// Returns the number of valid pairs ` `    ``static` `int` `countPairs(``int` `[]arr, ``int` `n) ` `    ``{ ` `        ``int` `numberOfPairs = 0; ` `     `  `        ``// Iterate over all possible pairs ` `        ``for` `(``int` `i = 0; i < n; i++) ` `            ``for` `(``int` `j = i + 1; j < n; j++) ` `                ``if` `(checkValidPair(arr[i], arr[j])) ` `                    ``numberOfPairs++; ` `     `  `        ``return` `numberOfPairs; ` `    ``} ` `     `  `    ``// Driver Code to test above functions ` `    ``static` `void` `Main() ` `    ``{ ` `        ``int` `[]arr = ``new` `int``[]{ 10, 12, 24 }; ` `        ``int` `n = arr.Length; ` `        ``Console.WriteLine(countPairs(arr, n)); ` `    ``} ` `} ` ` `  `// This code is contributed by manish shaw. `

## PHP

 ` `