Find a triplet (A, B, C) such that 3*A + 5*B + 7*C is equal to N

Find a triplet (A, B, C) such that 3*A + 5*B + 7*C is equal to N

Given an integer N, the task is to find three positive integers A, B, and C such that the value of the expression (3*A + 5*B + 7*C) is equal to N. If no such triplet exists, then print “-1”.

Examples:

Input: N = 19
Output:
A = 0
B = 1
C = 2
Explanation: Setting A, B, and C equal to 0, 1, and 2 respectively, the evaluated value of the expression = 3 * A + 5 * B + 7 * C = 3 * 0 + 5 * 1 + 7 * 2 = 19, which is the same as N (= 19).

Input: N = 4
Output: -1

Naive Approach: The simplest approach to solve the problem is to generate all possible triplets with integers up to N and check if there exists any triplet (A, B, C), such that the value of (3*A + 5*B + 7*C) is equal to N. If found to be true, then print that triplet. Otherwise, print “-1”.
Time Complexity: O(N³)
Auxiliary Space: O(1)

Efficient Approach: The above approach can be optimized based on the following observation that the value of A lies over the range [0, N / 3], the value of B lies over the range [0, N / 5], and the value of C lies over the range [0, N / 7]. Follow the steps below to solve the problem:

• Iterate over the range [0, N/7] and perform the following operations:
• After completing the above steps, if there doesn’t exist any such triplet then print “-1”.

Below is the implementation of the above approach:

Python3

def CalculateValues(N):               for C in range(0, N//7 + 1):                             for B in range(0, N//5 + 1):                             A = N - 7 * C - 5 * B                                          if (A >= 0 and A % 3 == 0):                 print("A =", A / 3, ", B =", B, ", \                        C =", C, sep =" ")                 return                 print(-1)     return       if __name__ == '__main__':          N = 19     CalculateValues(19)

Output:

A = 3.0 , B = 2 ,                        C = 0

Time Complexity: O(N²)
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)