Given an integer N (N ? 3), two distinct numbers X and Y, the task is to find the maximum number of possible ways by which a third drawn number (the third number lies in range [1, N]) can make a triplet of consecutive with given two numbers. Also, print the triplets.
Examples:
Input: N = 3, X = 2, Y = 3
Output:1
1 2 3
Explanation: There is only 1 way to make consecutive series of X and Y with
3rd drawn number which is 1.Input: N = 5, X = 2, Y = 5
Output: 0
Explanation: There are no possible ways to make form a triplet
of consecutive numbers having 2 and 5 in the triplet.
Approach: To solve the problem follow the below idea:
The problem can be solved by observing absolute difference between X and Y. There will be three cases on the basis of difference between X and Y, Which are explained below.
Observation of Possible cases:
Consider N = 5 for all inputs and X and Y are defined for each case separately.
Case 1: When the absolute difference between X and Y is 1:
There will be three types of cases for the difference equal to 1. In the first case, If Min(X, Y) is equal to 1 and in other cases, When
Max(X, Y) = N.
- When Min(X, Y) = 1 Then there will be only 1 possible case, Let X = 2, Y = 1.So, the consecutive array will be = {1, 2, 3}
- When Max(X, Y) = N Then there will be only 1 possible case, Let X = 5, Y = 4.So, the consecutive array will be = {3, 4, 5}
- For the rest of the cases: The rest of the cases excluding the above two discussed sub-cases will have two possible ways of making a consecutive array. Let X =2 and Y = 3.Then, there are two consecutive arrays are possible {1, 2, 3} and (2, 3, 4).
Case 2: When the absolute difference between X and Y is 2:
There will be only one possible case. Let X = 5 and Y = 3, Then only the occurrence of 4 can make a consecutive array = {3, 4, 5} in which the third drawn number will be mean of X and Y.
Case 3: When the absolute difference between X and Y is greater than 2: There will be no possible case by which you can make a consecutive array with X and Y.
Follow the steps to solve the problem:
- Obtain the absolute difference between X and Y.
- If the absolute difference is equal to 2 then the third number will be the mean of X and Y as discussed in Case 2.
- If the absolute difference is equal to 1, Then only for corner cases there will be one possible consecutive array as discussed in Case 1, Rest of the cases will have two consecutive arrays.
- If the absolute difference is greater than 2. Then, there will no possible consecutive array for such cases.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;void findTriplet(int X, int Y, int N){ // Array initialized to hold // consecutive array numbers int arr[3] = { 0 }; // Condition when absolute // difference between X and Y is 2 if (abs(X - Y) == 2) { // Printing possible number // of cases cout << "1\n"; arr[0] = X; arr[2] = Y; arr[1] = (X + Y) / 2; // Printing consecutive // array elements cout << arr[0] << " " << arr[1] << " " << arr[2] << "\n"; } // Condition when absolute // difference between X and Y is 1 else if (abs(X - Y) == 1) { // If one from X and Y is // equal to 1 if (min(X, Y) == 1) { // Printing possible // number of cases cout << "1\n"; arr[0] = 1; arr[1] = max(X, Y); arr[2] = max(X, Y) + 1; // Printing consecutive // array elements cout << arr[0] << " " << arr[1] << " " << arr[2] << "\n"; } else if (max(X, Y) == N) { // Printing possible // number of cases cout << "1\n"; arr[0] = min(X, Y) - 1; arr[1] = min(X, Y); arr[2] = max(X, Y); // Printing consecutive // array elements cout << arr[0] << " " << arr[1] << " " << arr[2] << "\n"; } // For cases when neither X // and nor Y is not equal // to 1 or N. else { // Printing possible cases cout << "2\n"; // Values of consecutive // numbers for first case arr[0] = min(X, Y) - 1; arr[1] = min(X, Y); arr[2] = max(X, Y); // Printing consecutive // array numbers cout << arr[0] << " " << arr[1] << " " << arr[2] << "\n"; // Values of consecutive // numbers for second case arr[0] = min(X, Y); arr[1] = max(X, Y); arr[2] = max(X, Y) + 1; // Printing consecutive // array numbers cout << arr[0] << " " << arr[1] << " " << arr[2] << "\n"; } } // When difference between X and Y // is greater than 2 else { cout << "0\n"; }}// Driver Codeint main(){ // Input value of N int N = 3; // input value of X and Y int X = 2, Y = 1; findTriplet(X, Y, N); return 0;}// This code is contributed by Rohit Pradhan |
Java
// Java code to implement the approachimport java.io.*;import java.lang.*;import java.util.*;public class GFG { // Driver function public static void main(String[] args) { // Input value of N int N = 3; // input value of X and Y int X = 2, Y = 1; findTriplet(X, Y, N); } static void findTriplet(int X, int Y, int N) { // Array initialized to hold // consecutive array numbers int[] arr = new int[3]; // Condition when absolute // difference between X and Y is 2 if (Math.abs(X - Y) == 2) { // Printing possible number // of cases System.out.println(1); arr[0] = X; arr[2] = Y; arr[1] = (X + Y) / 2; // Printing consecutive // array elements System.out.println(arr[0] + " " + arr[1] + " " + arr[2]); } // Condition when absolute // difference between X and Y is 1 else if (Math.abs(X - Y) == 1) { // If one from X and Y is // equal to 1 if (Math.min(X, Y) == 1) { // Printing possible // number of cases System.out.println(1); arr[0] = 1; arr[1] = Math.max(X, Y); arr[2] = Math.max(X, Y) + 1; // Printing consecutive // array elements System.out.println(arr[0] + " " + arr[1] + " " + arr[2]); } else if (Math.max(X, Y) == N) { // Printing possible // number of cases System.out.println(1); arr[0] = Math.min(X, Y) - 1; arr[1] = Math.min(X, Y); arr[2] = Math.max(X, Y); // Printing consecutive // array elements System.out.println(arr[0] + " " + arr[1] + " " + arr[2]); } // For cases when neither X // and nor Y is not equal // to 1 or N. else { // Printing possible cases System.out.println(2); // Values of consecutive // numbers for first case arr[0] = Math.min(X, Y) - 1; arr[1] = Math.min(X, Y); arr[2] = Math.max(X, Y); // Printing consecutive // array numbers System.out.println(arr[0] + " " + arr[1] + " " + arr[2]); // Values of consecutive // numbers for second case arr[0] = Math.min(X, Y); arr[1] = Math.max(X, Y); arr[2] = Math.max(X, Y) + 1; // Printing consecutive // array numbers System.out.println(arr[0] + " " + arr[1] + " " + arr[2]); } } // When difference between X and Y // is greater than 2 else { System.out.println(0); } }} |
Python3
# Python code to implement the approachdef findTriplet(X,Y,N): # Array initialized to hold consecutive array numbers arr = [0,0,0] # Condition when absolute difference between X and Y is 2 if(abs(X-Y) == 2): print(1) # Printing possible number of cases arr[0] = X arr[2] = Y arr[1] = (X + Y)//2 # Printing consecutive array elements print(arr[0],end=' ') print(arr[1],end=' ') print(arr[2]) # Condition when absolute difference between X and Y is 1 elif(abs(X-Y) == 1): # If one from X and Y is equal to 1 if(X == 1 or Y == 1): # Printing possible number of cases print(1) arr[0] = 1 if(X > Y): arr[1] = X else: arr[1] = Y arr[2] = arr[1] + 1 # Printing consecutive array elements print(arr[0],end=' ') print(arr[1],end=' ') print(arr[2]) elif(X == N or Y == N): # Printing possible number of cases print(1) if(X > Y): arr[0] = Y - 1 else: arr[0] = X - 1 arr[1] = arr[0] + 1 arr[2] = X + Y - arr[1] # Printing consecutive array elements print(arr[0],end=' ') print(arr[1],end=' ') print(arr[2]) # For cases when neither X and nor Y is not equal to 1 or N. else: # Printing possible cases print(2) # Values of consecutive numbers for first case if(X > Y): arr[0] = Y - 1 else: arr[0] = X - 1 arr[1] = arr[0] + 1 arr[2] = X + Y - arr[1] # Printing consecutive array numbers print(arr[0],end = ' ') print(arr[1],end = ' ') print(arr[2]) # Values of consecutive numbers for second case if(X > Y): arr[0] = Y arr[1] = X arr[2] = X + 1 else: arr[0] = X arr[1] = Y arr[2] = Y + 1 # Printing consecutive array numbers print(arr[0],end=' ') print(arr[1],end=' ') print(arr[2]) # When difference between X and Y is greater than 2 else: print(0) # Driver Codeif __name__ == "__main__": # Input value of N N = 3 # input value of X and Y X = 2 Y = 1 findTriplet(X,Y,N) # This code is contributed by ajaymakvana. |
C#
// C# code to implement the above approachusing System;public class GFG{ // Driver function public static void Main(string[] args) { // Input value of N int N = 3; // input value of X and Y int X = 2, Y = 1; findTriplet(X, Y, N); } static void findTriplet(int X, int Y, int N) { // Array initialized to hold // consecutive array numbers int[] arr = new int[3]; // Condition when absolute // difference between X and Y is 2 if (Math.Abs(X - Y) == 2) { // Printing possible number // of cases Console.WriteLine(1); arr[0] = X; arr[2] = Y; arr[1] = (X + Y) / 2; // Printing consecutive // array elements Console.WriteLine(arr[0] + " " + arr[1] + " " + arr[2]); } // Condition when absolute // difference between X and Y is 1 else if (Math.Abs(X - Y) == 1) { // If one from X and Y is // equal to 1 if (Math.Min(X, Y) == 1) { // Printing possible // number of cases Console.WriteLine(1); arr[0] = 1; arr[1] = Math.Max(X, Y); arr[2] = Math.Max(X, Y) + 1; // Printing consecutive // array elements Console.WriteLine(arr[0] + " " + arr[1] + " " + arr[2]); } else if (Math.Max(X, Y) == N) { // Printing possible // number of cases Console.WriteLine(1); arr[0] = Math.Min(X, Y) - 1; arr[1] = Math.Min(X, Y); arr[2] = Math.Max(X, Y); // Printing consecutive // array elements Console.WriteLine(arr[0] + " " + arr[1] + " " + arr[2]); } // For cases when neither X // and nor Y is not equal // to 1 or N. else { // Printing possible cases Console.WriteLine(2); // Values of consecutive // numbers for first case arr[0] = Math.Min(X, Y) - 1; arr[1] = Math.Min(X, Y); arr[2] = Math.Max(X, Y); // Printing consecutive // array numbers Console.WriteLine(arr[0] + " " + arr[1] + " " + arr[2]); // Values of consecutive // numbers for second case arr[0] = Math.Min(X, Y); arr[1] = Math.Max(X, Y); arr[2] = Math.Max(X, Y) + 1; // Printing consecutive // array numbers Console.WriteLine(arr[0] + " " + arr[1] + " " + arr[2]); } } // When difference between X and Y // is greater than 2 else { Console.WriteLine(0); } }}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript code to implement the approach const findTriplet = (X, Y, N) => { // Array initialized to hold // consecutive array numbers let arr = new Array(3).fill(0); // Condition when absolute // difference between X and Y is 2 if (Math.abs(X - Y) == 2) { // Printing possible number // of cases document.write("1<br/>"); arr[0] = X; arr[2] = Y; arr[1] = parseInt((X + Y) / 2); // Printing consecutive // array elements document.write(`${arr[0]} ${arr[1]} ${arr[2]}<br/>`); } // Condition when absolute // difference between X and Y is 1 else if (Math.abs(X - Y) == 1) { // If one from X and Y is // equal to 1 if (Math.min(X, Y) == 1) { // Printing possible // number of cases document.write("1<br/>"); arr[0] = 1; arr[1] = Math.max(X, Y); arr[2] = Math.max(X, Y) + 1; // Printing consecutive // array elements document.write(`${arr[0]} ${arr[1]} ${arr[2]}<br/>`); } else if (Math.max(X, Y) == N) { // Printing possible // number of cases document.write("1<br/>"); arr[0] = Math.min(X, Y) - 1; arr[1] = Math.min(X, Y); arr[2] = Math.max(X, Y); // Printing consecutive // array elements document.write(`${arr[0]} ${arr[1]} ${arr[2]}<br/>`); } // For cases when neither X // and nor Y is not equal // to 1 or N. else { // Printing possible cases document.write("2<br/>"); // Values of consecutive // numbers for first case arr[0] = Math.min(X, Y) - 1; arr[1] = Math.min(X, Y); arr[2] = Math.max(X, Y); // Printing consecutive // array numbers document.write(`${arr[0]} ${arr[1]} ${arr[2]}<br/>`); // Values of consecutive // numbers for second case arr[0] = Math.min(X, Y); arr[1] = Math.max(X, Y); arr[2] = Math.max(X, Y) + 1; // Printing consecutive // array numbers document.write(`${arr[0]} ${arr[1]} ${arr[2]}<br/>`); } } // When difference between X and Y // is greater than 2 else { document.write("0<br/>"); } } // Driver function // Input value of N let N = 3; // input value of X and Y let X = 2, Y = 1; findTriplet(X, Y, N); // This code is contributed by rakeshsahni</script> |
Output
1 1 2 3
Time Complexity: O(1)
Auxiliary Space: O(1)
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
