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 = 3
B = 2
C = 0
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 * 3 + 5 * 2 + 7 * 0 = 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(N3)
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:
- Iterate over the range [0, N/5] and find the value of A as (N – 5*j – 7*i).
- In the above step, if the value of A is at least 0 and A is divisible by 3, then there exists one such triplet as (A/3, i, j). Print this triplet and break out of the loop.
- After completing the above steps, if there doesn’t exist any such triplet then print “-1”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find a triplet (A, B, C)// such that 3 * A + 5 * B + 7 * C is Nvoid CalculateValues(int N){ int A = 0, B = 0, C = 0; // Iterate over the range [0, N//7] for (C = 0; C < N/7; C++) { // Iterate over the range [0, N//5] for ( B = 0; B < N/5; B++) { // Find the value of A int A = N - 7 * C - 5 * B; // If A is greater than or equal // to 0 and divisible by 3 if (A >= 0 && A % 3 == 0) { cout << "A = " << A / 3 << ", B = " << B << ", C = "<< C << endl; return; } } } // Otherwise, print -1 cout << -1 << endl;}// Driver Codeint main(){ int N = 19; CalculateValues(19); return 0;}// This code is contributed by susmitakundugoaldanga. |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{ // Function to find a triplet (A, B, C) // such that 3 * A + 5 * B + 7 * C is N static void CalculateValues(int N) { int A = 0, B = 0, C = 0; // Iterate over the range [0, N//7] for (C = 0; C < N/7; C++) { // Iterate over the range [0, N//5] for ( B = 0; B < N/5; B++) { // Find the value of A A = N - 7 * C - 5 * B; // If A is greater than or equal // to 0 and divisible by 3 if (A >= 0 && A % 3 == 0) { System.out.print("A = " + A / 3 + ", B = " + B + ", C = "+ C); return; } } } // Otherwise, print -1 System.out.println(-1); } // Driver Code public static void main(String[] args) { int N = 19; CalculateValues(19); }}// This code is contributed by souravghosh0416. |
Python3
# Python program for the above approach# Function to find a triplet (A, B, C)# such that 3 * A + 5 * B + 7 * C is Ndef CalculateValues(N): # Iterate over the range [0, N//7] for C in range(0, N//7 + 1): # Iterate over the range [0, N//5] for B in range(0, N//5 + 1): # Find the value of A A = N - 7 * C - 5 * B # If A is greater than or equal # to 0 and divisible by 3 if (A >= 0 and A % 3 == 0): print("A =", A / 3, ", B =", B, ", \ C =", C, sep =" ") return # Otherwise, print -1 print(-1) return# Driver Codeif __name__ == '__main__': N = 19 CalculateValues(19) |
C#
// C# program for the above approachusing System;class GFG{ // Function to find a triplet (A, B, C) // such that 3 * A + 5 * B + 7 * C is N static void CalculateValues(int N) { int A = 0, B = 0, C = 0; // Iterate over the range [0, N//7] for (C = 0; C < N/7; C++) { // Iterate over the range [0, N//5] for ( B = 0; B < N/5; B++) { // Find the value of A A = N - 7 * C - 5 * B; // If A is greater than or equal // to 0 and divisible by 3 if (A >= 0 && A % 3 == 0) { Console.Write("A = " + A / 3 + ", B = " + B + ", C = "+ C); return; } } } // Otherwise, print -1 Console.WriteLine(-1); } // Driver Code static public void Main() { int N = 19; CalculateValues(19); }}// This code is contributed by splevel62. |
Javascript
<script>// Javascript program for the above approach// Function to find a triplet (A, B, C)// such that 3 * A + 5 * B + 7 * C is Nfunction CalculateValues(N){var A = 0, B = 0, C = 0;// Iterate over the range [0, N//7]for (C = 0; C < N/7; C++){ // Iterate over the range [0, N//5] for ( B = 0; B < N/5; B++) { // Find the value of A var A = N - 7 * C - 5 * B; // If A is greater than or equal // to 0 and divisible by 3 if (A >= 0 && A % 3 == 0) { document.write( "A = " + A / 3 + ", B = " + B + ", C = "+ C ); return; } }}// Otherwise, print -1document.write( -1 );}// Driver Codevar N = 19;CalculateValues(19);</script> |
A = 3, B = 2, C = 0
Time Complexity: O(N2)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!