Given an array arr[] of size N, the task is to count the pairs whose concatenation of elements is divisible by 3 and each array element present in at most one pair.
Examples:
Input: arr[] = { 5, 3, 2, 8, 7 }
Output: 1
Explanation:
Possible pairs whose concatenation is divisible by 3 are { 27, 72, 78, 87 }, but the array element arr[4] will be present in at most one pair. Therefore, the required output is 1Input: arr[] = { 10, 6, 3, 7, 2 }
Output: 2
Naive approach: The simplest approach to solve this problem is to traverse the array and generate all possible pairs of the given array. For each pair check if the concatenation of elements of the pair is divisible by 3 or not. If found to be true, then mark both the element as false, so that both the elements of the pair can’t be present in more than one pair.
Below is the implementation of the naive approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to count pairs whose concatenation// is divisible by 3 and each element can be// present in at most one pairint countDivBy3InArray(int arr[], int N){ // Stores count pairs whose concatenation // is divisible by 3 and each element can // be present in at most one pair int ans = 0; // Check if an element present // in any pair or not bool taken[N]; memset(taken, false, sizeof(taken)); // Generate all possible pairs for(int i = 0; i < N; i++) { // If the element already // present in a pair if (taken[i] == true) { continue; } for(int j = i + 1; j < N; j++) { // If the element already // present in a pair if (taken[j] == true) { continue; } // If concatenation of elements // is divisible by 3 if (stoi(to_string(arr[i]) + to_string(arr[j])) % 3 == 0 || stoi(to_string(arr[j]) + to_string(arr[i])) % 3 == 0) { // Update ans ans += 1; // Mark i is True taken[i] = true; // Mark j is True taken[j] = true; } } } return ans;}int main(){ int arr[] = { 5, 3, 2, 8, 7 }; int N = sizeof(arr) / sizeof(arr[0]); // To display the result cout << countDivBy3InArray(arr, N); return 0;} |
Java
// Java program to implement// the above approachimport java.io.*;import java.util.Arrays;class GFG{// Function to count pairs whose concatenation // is divisible by 3 and each element can be// present in at most one pairpublic static int countDivBy3InArray(int[] arr){ // Stores count pairs whose concatenation // is divisible by 3 and each element can // be present in at most one pair int ans = 0; // Check if an element present // in any pair or not boolean[] taken = new boolean[arr.length]; Arrays.fill(taken, false); // Generate all possible pairs for(int i = 0; i < arr.length; i++) { // If the element already // present in a pair if (taken[i] == true) { continue; } for(int j = i + 1; j < arr.length; j++) { // If the element already // present in a pair if (taken[j] == true) { continue; } // If concatenation of elements // is divisible by 3 if (Integer.parseInt( Integer.toString(arr[i]) + Integer.toString(arr[j])) % 3 == 0 || Integer.parseInt( Integer.toString(arr[j]) + Integer.toString(arr[i])) % 3 == 0) { // Update ans ans += 1; // Mark i is True taken[i] = true; // Mark j is True taken[j] = true; } } } return ans;}// Driver Codepublic static void main(String[] args){ int[] arr = { 5, 3, 2, 8, 7 }; // To display the result System.out.println(countDivBy3InArray(arr));}}// This code is contributed by aditya7409 |
Python3
# Python3 program to implement# the above approach# Function to count pairs whose concatenation is# divisible by 3 and each element can be present# in at most one pair def countDivBy3InArray(arr): # Stores count pairs whose concatenation is # divisible by 3 and each element can be present # in at most one pair ans = 0 # Check if an element present # in any pair or not taken = [False] * len(arr) # Generate all possible pairs for i in range(len(arr)): # If the element already # present in a pair if taken[i]: continue for j in range(i + 1, len(arr)): # If the element already # present in a pair if taken[j]: continue # If concatenation of elements # is divisible by 3 if (not int(str(arr[i])+str(arr[j])) % 3 or not int(str(arr[j])+str(arr[i])) % 3): # Update ans ans += 1 # Mark i is True taken[i] = True # Mark j is True taken[j] = True return ans# Driver Codearr = [5, 3, 2, 8, 7]# To display the resultprint(countDivBy3InArray(arr)) |
C#
// C# program to implement// the above approachusing System;public class GFG{ // Function to count pairs whose concatenation // is divisible by 3 and each element can be // present in at most one pair public static int countDivBy3InArray(int[] arr) { // Stores count pairs whose concatenation // is divisible by 3 and each element can // be present in at most one pair int ans = 0; // Check if an element present // in any pair or not bool[] taken = new bool[arr.Length]; // Generate all possible pairs for(int i = 0; i < arr.Length; i++) { // If the element already // present in a pair if (taken[i] == true) { continue; } for(int j = i + 1; j < arr.Length; j++) { // If the element already // present in a pair if (taken[j] == true) { continue; } // If concatenation of elements // is divisible by 3 if (Int32.Parse( (arr[i]).ToString() + (arr[j]).ToString()) % 3 == 0 || Int32.Parse( (arr[j]).ToString() + (arr[i]).ToString()) % 3 == 0) { // Update ans ans += 1; // Mark i is True taken[i] = true; // Mark j is True taken[j] = true; } } } return ans; } // Driver Code public static void Main(String[] args) { int[] arr = { 5, 3, 2, 8, 7 }; // To display the result Console.WriteLine(countDivBy3InArray(arr)); }}// This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to implement the above approach // Function to count pairs whose concatenation // is divisible by 3 and each element can be // present in at most one pair function countDivBy3InArray(arr) { // Stores count pairs whose concatenation // is divisible by 3 and each element can // be present in at most one pair let ans = 0; // Check if an element present // in any pair or not let taken = new Array(arr.length); taken.fill(false); // Generate all possible pairs for(let i = 0; i < arr.length; i++) { // If the element already // present in a pair if (taken[i] == true) { continue; } for(let j = i + 1; j < arr.length; j++) { // If the element already // present in a pair if (taken[j] == true) { continue; } // If concatenation of elements // is divisible by 3 if (parseInt((arr[i]).toString() + (arr[j]).toString(), 10) % 3 == 0 || parseInt((arr[j]).toString() + (arr[i]).toString(), 10) % 3 == 0) { // Update ans ans += 1; // Mark i is True taken[i] = true; // Mark j is True taken[j] = true; } } } return ans; } let arr = [ 5, 3, 2, 8, 7 ]; // To display the result document.write(countDivBy3InArray(arr)); </script> |
Output:
1
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient approach: The above approach can be optimized by using the concept of checking a number is divisible by 3 or not. Follow the steps below to solve the problem:
- Initialize three variables, say rem0, rem1 and rem2, to store the count of array elements whose remainder is 0, 1 and 2 respectively when divided by 3.
- Traverse the array and check for the following conditions:
- If arr[i] %3 == 0, then update cnt0 += 1.
- If arr[i] %3 == 1, then update cnt1 += 1.
- If arr[i] %3 == 2, then update cnt2 += 1.
- Finally, print the count of pairs, i.e. (rem0 / 2 + min(rem1, rem2)).
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to count pairs whose concatenation is// divisible by 3 and each element can be present// in at most one pairint countDiv(int arr[], int n){ // Stores count of array elements whose // remainder is 0 by taking modulo by 3 int rem0 = 0; // Stores count of array elements whose // remainder is 1 by taking modulo by 3 int rem1 = 0; // Stores count of array elements whose // remainder is 2 by taking modulo by 3 int rem2 = 0; // Traverse the array for(int i = 0; i < n; i++) { // Stores sum of digits // of arr[i] int digitSum = 0; // Update digitSum digitSum += arr[i]; // If remainder of digitSum by // by taking modulo 3 is 0 if (digitSum % 3 == 0) { // Update rem0 rem0 += 1; } // If remainder of digitSum by // by taking modulo 3 is 1 else if (digitSum % 3 == 1) { // Update rem1 rem1 += 1; } else { // Update rem2 rem2 += 1; } } return (rem0 / 2 + min(rem1, rem2));}// Driver codeint main(){ int arr[] = { 5, 3, 2, 8, 7 }; int n = sizeof(arr) / sizeof(arr[0]); // To display the result cout << (countDiv(arr, n));}// This code is contributed by ukasp |
Java
// Java program to implement// the above approach public class GFG{ // Function to count pairs whose concatenation is // divisible by 3 and each element can be present // in at most one pair static int countDiv(int[] arr) { // Stores count of array elements whose // remainder is 0 by taking modulo by 3 int rem0 = 0; // Stores count of array elements whose // remainder is 1 by taking modulo by 3 int rem1 = 0; // Stores count of array elements whose // remainder is 2 by taking modulo by 3 int rem2 = 0; // Traverse the array for(int i : arr) { // Stores sum of digits // of arr[i] int digitSum = 0; // Update digitSum digitSum += i; // If remainder of digitSum by // by taking modulo 3 is 0 if(digitSum % 3 == 0) { // Update rem0 rem0 += 1; } // If remainder of digitSum by // by taking modulo 3 is 1 else if(digitSum % 3 == 1) { // Update rem1 rem1 += 1; } else { // Update rem2 rem2 += 1; } } return (rem0 / 2 + Math.min(rem1, rem2)); } // Driver code public static void main(String[] args) { int[] arr = {5, 3, 2, 8, 7}; // To display the result System.out.println(countDiv(arr)); }}// This code is contributed by divyesh072019. |
Python3
# Python3 program to implement# the above approach# Function to count pairs whose concatenation is# divisible by 3 and each element can be present# in at most one pair def countDiv(arr): # Stores count of array elements whose # remainder is 0 by taking modulo by 3 rem0 = 0 # Stores count of array elements whose # remainder is 1 by taking modulo by 3 rem1 = 0 # Stores count of array elements whose # remainder is 2 by taking modulo by 3 rem2 = 0 # Traverse the array for i in arr: # Stores sum of digits # of arr[i] digitSum = 0 for digit in str(i): # Update digitSum digitSum += int(digit) # If remainder of digitSum by # by taking modulo 3 is 0 if digitSum % 3 == 0: # Update rem0 rem0 += 1 # If remainder of digitSum by # by taking modulo 3 is 1 elif digitSum % 3 == 1: # Update rem1 rem1 += 1 else: # Update rem2 rem2 += 1 return (rem0 // 2 + min(rem1, rem2))# Driver Codearr = [5, 3, 2, 8, 7]# To display the resultprint(countDiv(arr)) |
C#
// C# program to implement// the above approach using System;using System.Collections.Generic;class GFG { // Function to count pairs whose concatenation is // divisible by 3 and each element can be present // in at most one pair static int countDiv(int[] arr) { // Stores count of array elements whose // remainder is 0 by taking modulo by 3 int rem0 = 0; // Stores count of array elements whose // remainder is 1 by taking modulo by 3 int rem1 = 0; // Stores count of array elements whose // remainder is 2 by taking modulo by 3 int rem2 = 0; // Traverse the array foreach(int i in arr) { // Stores sum of digits // of arr[i] int digitSum = 0; // Update digitSum digitSum += i; // If remainder of digitSum by // by taking modulo 3 is 0 if(digitSum % 3 == 0) { // Update rem0 rem0 += 1; } // If remainder of digitSum by // by taking modulo 3 is 1 else if(digitSum % 3 == 1) { // Update rem1 rem1 += 1; } else { // Update rem2 rem2 += 1; } } return (rem0 / 2 + Math.Min(rem1, rem2)); } // Driver code static void Main() { int[] arr = {5, 3, 2, 8, 7}; // To display the result Console.Write(countDiv(arr)); }}// This code is contributed by divyeshrabadiya07. |
Javascript
<script> // Javascript program to implement // the above approach // Function to count pairs // whose concatenation is // divisible by 3 and each // element can be present // in at most one pair function countDiv(arr) { // Stores count of array elements whose // remainder is 0 by taking modulo by 3 let rem0 = 0; // Stores count of array elements whose // remainder is 1 by taking modulo by 3 let rem1 = 0; // Stores count of array elements whose // remainder is 2 by taking modulo by 3 let rem2 = 0; // Traverse the array for(let i = 0; i < arr.length; i++) { // Stores sum of digits // of arr[i] let digitSum = 0; // Update digitSum digitSum += arr[i]; // If remainder of digitSum by // by taking modulo 3 is 0 if(digitSum % 3 == 0) { // Update rem0 rem0 += 1; } // If remainder of digitSum by // by taking modulo 3 is 1 else if(digitSum % 3 == 1) { // Update rem1 rem1 += 1; } else { // Update rem2 rem2 += 1; } } return (parseInt(rem0 / 2, 10) + Math.min(rem1, rem2)); } let arr = [5, 3, 2, 8, 7]; // To display the result document.write(countDiv(arr)); </script> |
Output:
1
Time Complexity: O(N)
Auxiliary Space: O()
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!
