Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem statement
1.1.
Example 1
1.1.1.
Input
1.1.2.
Output
1.1.3.
Explanation
2.
Approach
3.
Brute force Code:
3.1.
Input:
3.2.
Output:
4.
Time Complexity 
5.
Space Complexity 
6.
Optimised Approach
7.
Optimised Code:
7.1.
Input:
7.2.
Output:
8.
Time Complexity 
9.
Space Complexity 
10.
Frequently Asked Questions
11.
Key Takeaways
Last Updated: Mar 27, 2024

Kunal and Triplets

Author Apoorv
0 upvote

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.

Recommended Topic, Array Implementation of Queue and  Rabin Karp Algorithm

Example 1

Input

5

2 5 6 1 3

Output

3

Explanation

The following triplets exist in the given array:

2 5 2

2 5 1

2 5 3

2 2 1

2 2 3

2 1 3

5 2 1

5 2 3

5 1 3

2 1 3

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
    
}

Input:

5
2 5 2 1 3

 

Output:

3

Time Complexity 

O(N ^ 3)

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).

Read More - Time Complexity of Sorting Algorithms

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.

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;
}

Input:

5
2 5 2 1 3

 

Output:

3

Time Complexity 

O(1)

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

 

  1. 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.
  2. What is ceil value?
    CEIL() returns the lowest integer value that is greater than or equal to a number.
  3. 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.

Recommended Readings:

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.

 

Previous article
Sort the matrix row-wise and column-wise
Next article
Sparse Table Construction (SUM QRY)
Live masterclass