Do you think IIT Guwahati certified course can help you in your career?
Problem statement
Aman and his best friend Kunal are now ending their school and soon they both will head separate ways…
Aman challenges his friend Kunal to solve a coding problem as Kunal is pro in computer science stuff but somehow Kunal is not able to solve the problem given by Aman and Kunal want to cheat and is seeking help from your side so please help Kunal to prove him in front of his best friend. So the question is that Kunal is Given an array of size N, which is a 0-indexed array.
Where ⌊.⌋ is the floor operator and Kunal has to compute the sum in the most optimized way, In the input, Kunal is given with the array size and array elements. Help Kunal to save his self-respect in front of his best friend Aman.
So, if we compute the required sum using these triplets, we get the sum to be equal to 3.
Approach
The brute force approach to solve this problem “operation on a Triplets of a given array” by Rohit is that we can iterate in a nested way to generate all the triplets and then perform the operation on the triplet obtained. After performing the operation on the triplet, continuously update your answer because we have to take summation of these operations for all the possible triplets, but doing so will cost high time complexity because in every case, we are iterating three times in an array which will cost the time complexity of O(N ^ 3) where ‘N’ is the total number of elements in the array. Below is the detailed code for this approach.
Brute force Code:
//c++ code for operation on a Triplets of given array
#include<bits/stdc++.h>
using namespace std;
int main(){
// Taking input
int n;
cin>>n;
int arr[n];
for(int i = 0 ; i < n ; i++)cin>>arr[i];
// Nested iteration for the calculation of the answer
int ans = 0;
// operation on a Triplets of given array
for(int i = 0 ; i < n ; i++){
for(int j = i+1 ; j < n ; j++){
for(int k = j+1 ; k < n ; k++){
ans += floor((arr[i]+arr[j]+arr[k])/(arr[i]*arr[j]*arr[k]));
}
}
}
cout<<ans;
return 0;
}
You can also try this code with Online C++ Compiler
The time complexity for the solution of operation on a Triplets of a given array is O(N ^ 3), where ‘N’ is the size of the given array. Since in the entire implementation, we are generating all the possible triplets for that, we are iterating three times in a nested loop. Iterating three times in a nested loop leads to the time complexity of O(N ^ 3).
The space complexity for the solution of operation on a Triplets of a given array is O(1). Since in the entire implementation, we have not used any extra data structure for the formulation, which means the work has been done in constant space.
Optimised Approach
So to optimise this approach, we can use the concept of Permutation and combination and some basic observation. In the above example, we have to find the floor value so whenever any of the values a,b,c is greater than three, and we are operating on that, then the answer obtained will always be 0.
Example a = 4,b = 2 ,c = 5
Then according to the this formula
[4+2+5 / 4*2*5] = 0
So we have to deal with only four to five cases individually and the rest of the cases will always give floor value as zero. All these cases are handled individually in the implementation given below. Whenever two numbers in the list are greater than three or all three numbers are greater than two, the floor value will always be 0.Below is the detailed algorithm and implementation of the given approach.
Optimised Code:
// Code for operation on a Triplets of given array
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long n;
// Taking the array size ;
cin >> n;
// input array declaration
long long arr[n];
// Maintaining the count of one two and three and other numbers
long long ones, twos, threes, others;
ones = twos = threes = others = 0;
for (int i = 0;i < n;i++)
{
cin >> arr[i];
if (arr[i] == 1)
{
ones++;
}
else if (arr[i] == 2)
{
twos++;
}
else if (arr[i] == 3)
{
threes++;
}
else
{
others++;
}
}
// To store the final computer answer
long long ans = 0;
//case: 1 1 1
ans = ((ones * (ones - 1) * (ones - 2)) / 2);
//case: 1 1 2
ans += ((ones*(ones - 1)))*(twos);
//case: 1 1 x
ans += ((ones*(ones - 1))/2)*(others+threes);
//case: 1 2 2
ans += ((twos*(twos - 1))/2)*(ones);
//case: 1 2 3
ans += (ones*twos*threes);
// Print the final answer operation on a Triplets of given array
cout << ans << endl;
return 0;
}
You can also try this code with Online C++ Compiler
The time complexity for the solution of operation on a Triplets of a given array is O(1). In the entire implementation, we have simply used the basic formulas of permutations and combinations, which can do the work for us in constant time.
Space Complexity
O(1)
The space complexity for the solution of operation on a Triplets of a given array is O(1). Since in the entire implementation, we have not used any extra data structure for the formulation, which means the work has been done in constant space.
Frequently Asked Questions
What is the floor value? Returns the integer that is the smallest or equal to a specified number. The floor is frequently used to round numbers. This is a function with only one value.
What is ceil value? CEIL() returns the lowest integer value that is greater than or equal to a number.
What was the intuition behind the optimised approach? Since it was clearly visible that only 4 to 5 cases will contribute in the final answer, rest will give answer 0 as floor values,so there is no need to traverse the array three times.
Key Takeaways
In this blog, we discussed the solution of the problem statement “operation on a Triplets of a given array ”.Along with the solution, We also explored both the approaches brute force and optimised approach along with their implementations with the time and space complexity of the solution.
If you want to learn more about such hidden algorithms and want to practice some quality questions which require you to excel your preparation s a notch higher, then you can visit our Guided Path for these algorithms on Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavours, and Keep Coding.
518+ registered 
