Given an array arr[] consisting of integer elements, find the number of triplets having distinct indices i, j, k where i < j < k, such that arr[i]*arr[j] = arr[j] + arr[k].
Examples:
Input: arr[] = {4, 4, 3, 12, 24, 36}
Output: 4
Explanation: There are 4 such pairs (4, 4, 12), (3, 12, 24), (3, 12, 24), (4, 12, 36) such that arr[i]*arr[j]=arr[j]+arr[k]Input: arr[] = {3, 16, 32, 2, 8, 12, 14, 28}
Output: 2
Explanation: There are 2 such pairs (3, 16, 32), (3, 14, 28) such that arr[i]*arr[j] = arr[j] + arr[k]
Naive Approach: To solve the problem follow the below steps:
- Iterate array arr[] from left to right such that for ith element loop is iterated from left to right for each jth element, including iteration for the kth element to form a triplet, holding the condition i<j<k.
- If the condition arr[i]*arr[j] = arr[j]+arr[k] satisfies then the counter is incremented by 1. The final count is the number of triplets and then print the final count as output.
Below is the implementation of the above approach:
C++
// C++ program for the naive approach#include <bits/stdc++.h>using namespace std;// Function to count triplets with the// given condition arr[i]*arr[j]=arr[j]+arr[k]int countTriplets(int arr[], int n){ int cnt = 0; for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n - 1; j++) { for (int k = j + 1; k < n; k++) { // If it satisfy the given // conditions then increase // counter if (arr[i] * arr[j] == arr[j] + arr[k]) { cnt += 1; } } } } return cnt;}// Driver Codeint main(){ // Given array arr[] int arr[] = { 4, 4, 3, 12, 24, 36 }; // Function Call cout << countTriplets(arr, 6) << endl; return 0;} |
Java
public class CountTriplets { // Function to count triplets with the given condition static int countTriplets(int[] arr, int n) { int cnt = 0; for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n - 1; j++) { for (int k = j + 1; k < n; k++) { // If it satisfies the given conditions, then increase counter if (arr[i] * arr[j] == arr[j] + arr[k]) { cnt++; } } } } return cnt; }// Driver Code public static void main(String[] args) { int[] arr = {4, 4, 3, 12, 24, 36}; System.out.println(countTriplets(arr, 6)); }} |
Python3
# python program for the naive approachdef countTriplets(arr, n): cnt = 0 for i in range(n - 2): for j in range(i + 1, n - 1): for k in range(j + 1, n): # If it satisfies the given conditions, then increase the counter if arr[i] * arr[j] == arr[j] + arr[k]: cnt += 1 return cnt# Driver Codeif __name__ == "__main__": # Given array arr[] arr = [4, 4, 3, 12, 24, 36] # Function Call print(countTriplets(arr, 6)) |
C#
using System;class Program{ // Function to count triplets with the given condition arr[i]*arr[j]=arr[j]+arr[k] static int CountTriplets(int[] arr) { int n = arr.Length; int count = 0; for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n - 1; j++) { for (int k = j + 1; k < n; k++) { // If it satisfies the given conditions, increase the counter if (arr[i] * arr[j] == arr[j] + arr[k]) { count++; } } } } return count; } static void Main() { // Given array arr[] int[] arr = { 4, 4, 3, 12, 24, 36 }; // Function Call Console.WriteLine(CountTriplets(arr)); }} |
Javascript
// Javascript program for the naive approach// Function to count triplets with the// given condition arr[i]*arr[j]===arr[j]+arr[k]function countTriplets(arr) { let cnt = 0; for (let i = 0; i < arr.length - 2; i++) { for (let j = i + 1; j < arr.length - 1; j++) { for (let k = j + 1; k < arr.length; k++) { // If it satisfy the given // conditions then increase // counter if (arr[i] * arr[j] === arr[j] + arr[k]) { cnt += 1; } } } } return cnt;}// Driver Code// Given array arr[]const arr = [4, 4, 3, 12, 24, 36];// Function Callconsole.log(countTriplets(arr)); |
Output
4
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: To solve the problem follow the below idea:
Given condition: arr[i]*arr[j] = arr[j]+arr[k], we can move arr[j] to the other side of this equation.
- arr[i] = (arr[j]+arr[k])/arr[j]
- arr[i] = 1 + arr[k]/arr[j]
Follow the steps to solve the problem:
- We will run nested for loops to find pair (j, k) such that j<k.
- If arr[j] is not zero and arr[k] is divisible by arr[j] then add the count of arr[i] to the total count.
- After the completion of the loop for the jth element, the jth element is now considered as the ith element, and the count of arr[i] is incremented by 1. Now, Move to step 1 if the loop iteration hasn’t ended yet.
- After the completion of loops, The final count is the number of triplets holding condition arr[i]*arr[j]=arr[i]+arr[k], and then print the final count as output.
Below is the implementation of the above approach:
C++
// C++ program for the efficient approach#include <bits/stdc++.h>using namespace std;// Function to count triplets with the given// condition arr[i]*arr[j]=arr[j]+arr[k]int countTriplets(int arr[], int n){ int cnt = 0; unordered_map<int, int> countARRi; for (int j = 0; j < n - 1; j++) { if (arr[j] != 0) { for (int k = j + 1; k < n; k++) { // If it satisfy that arr[k] // is divisible by arr[j] then // increment counter by // countArri[1+arr[k]/arr[j]]; // here countArri is a map which // stores count of arr[i] // computed previously. if (arr[k] % arr[j] == 0) { cnt += countARRi[1 + arr[k] / arr[j]]; } } } countARRi[arr[j]]++; } return cnt;}// Driver Codeint main(){ // Given array arr[] int arr[] = { 3, 16, 32, 2, 8, 12, 14, 28 }; // Function Call cout << countTriplets(arr, 8) << endl; return 0;} |
Java
import java.util.HashMap;import java.util.Map;public class CountTriplets { // Function to count triplets with the given condition static int countTriplets(int[] arr, int n) { int cnt = 0; Map<Integer, Integer> countARRi = new HashMap<>(); for (int j = 0; j < n - 1; j++) { if (arr[j] != 0) { for (int k = j + 1; k < n; k++) { // If it satisfies that arr[k] is divisible by arr[j] // then increment the counter by countARRi.get(1 + arr[k] / arr[j]); if (arr[k] % arr[j] == 0) { cnt += countARRi.getOrDefault(1 + arr[k] / arr[j], 0); } } } countARRi.put(arr[j], countARRi.getOrDefault(arr[j], 0) + 1); } return cnt; } // Driver code public static void main(String[] args) { // Given array arr[] int[] arr = {3, 16, 32, 2, 8, 12, 14, 28}; // Function Call System.out.println(countTriplets(arr, 8)); }} |
Python3
import collections# Function to count triplets with the given# condition arr[i]*arr[j]=arr[j]+arr[k]def countTriplets(arr, n): cnt = 0 countARRi = collections.defaultdict(int) for j in range(n - 1): if arr[j] != 0: for k in range(j + 1, n): # If it satisfy that arr[k] # is divisible by arr[j] then # increment counter by # countArri[1+arr[k]/arr[j]]; # here countArri is a map which # stores count of arr[i] # computed previously. if arr[k] % arr[j] == 0: cnt += countARRi[1 + arr[k] // arr[j]] countARRi[arr[j]] += 1 return cnt# Driver Codearr = [3, 16, 32, 2, 8, 12, 14, 28]print(countTriplets(arr, 8)) |
C#
using System;using System.Collections.Generic;class GFG{ // Function to count triplets with // given condition arr[i]*arr[j]=arr[j]+arr[k] static int CountTriplets(int[] arr, int n) { int cnt = 0; Dictionary<int, int> countARRi = new Dictionary<int, int>(); for (int j = 0; j < n - 1; j++) { if (arr[j] != 0) { for (int k = j + 1; k < n; k++) { // If it satisfies that arr[k] is divisible by arr[j]. if (arr[k] % arr[j] == 0) { if (countARRi.ContainsKey(1 + arr[k] / arr[j])) { cnt += countARRi[1 + arr[k] / arr[j]]; } } } } if (countARRi.ContainsKey(arr[j])) { countARRi[arr[j]]++; } else { countARRi.Add(arr[j], 1); } } return cnt; } static void Main(string[] args) { // Given array arr[] int[] arr = { 3, 16, 32, 2, 8, 12, 14, 28 }; // The Function Call Console.WriteLine(CountTriplets(arr, 8)); }} |
Javascript
// Function to count triplets with the given conditionfunction countTriplets(arr) { let cnt = 0; const countARRi = new Map(); for (let j = 0; j < arr.length - 1; j++) { if (arr[j] !== 0) { for (let k = j + 1; k < arr.length; k++) { // If it satisfies that arr[k] is divisible by arr[j] if (arr[k] % arr[j] === 0) { // Increment the counter by countARRi[1 + arr[k] / arr[j]] // Here countARRi is a map that stores the count of arr[i] computed previously. cnt += countARRi.get(1 + arr[k] / arr[j]) || 0; } } } countARRi.set(arr[j], (countARRi.get(arr[j]) || 0) + 1); } return cnt;}// Driver Codeconst arr = [3, 16, 32, 2, 8, 12, 14, 28];// Function Callconsole.log(countTriplets(arr)); |
Output
2
Time Complexity: O(N2)
Auxiliary Space: O(N)
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