Find X such that the given expression is maximized
Given two integers A and B, the task is to output the maximum value of (X % B) * ((A − X) % B) by finding the appropriate value of X such that (0 <= X <= A).
Note: If there are multiple values of X, output any valid value.
Examples:
Input: A = 4, B = 7
Output: 2
Explanation: As we know choose the value of X from the range [0, A], Let’s check for each value:
- For X = 0: (0%7) * (4%7) = 0
- For X = 1: (1%7) * (3%7) = 3
- For X = 2: (2%7) * (2%7) = 4
- For X = 3: (3%7) * (1%7) = 3
- For X = 4: (4%7) * (0%7) = 0
- At X = 2, the given expression gives a maximum value of 4. Therefore, X = 2 is the only valid value for a given expression.
Input: A = 8, B = 3
Output: 4
Explanation: The expression’s value will be 0 for {0, 2, 3, 5, 6, 8} and 1 for {1, 4, 7}. The maximum value of the expression that can be attained is 1, by any value of X from {1, 4, 7}. Thus, 4 is a valid value of X. Note that 1 and 7 are also valid as there can be multiple answers.
Approach: Implement the idea below to solve the problem
We can choose X from 0 to min(A, B – 1).
Reason: We always mod B with both terms. Hence, the highest value of (X % B) and ((A – X) % B) can be B – 1. Also, we need to choose X between 0 and N (inclusive of both). Now, Consider an example: A = 4 and B = 7
- (X % B) can be [0, 1, 2, 3, 4] (i.e) X value
- ((A – X) % B) will be the rotated version of this based on A value. Here it is [4, 3, 2, 1, 0]
- Now we need to find the maximum value of multiplication from the above 2 list of values and output it’s corresponding X value.
We know that X is always between 0 <= X <= min(A, B-1)
Now if, A = 8 and B = 6
- (X % B) can be [0, 1, 2, 3, 4, 5]
- ((A – X) % B) will be [2, 1, 0, 5, 4, 3]
- Here when X = 4, We get 4 * 4 = 16 (max), Hence we choose this X. This formula will be used for the calculations.
Steps were taken to solve the problem:
- Declare a variable let say G, and initialize it equal to min(A, B – 1)
- If (G == 0)
- Output G
- Else
- Declare variable i as ((A – G) % B)
- Declare variable j = ((G / 2) + (G % 2))
- Output (i + j)/2
Code to implement the approach:
C++
#include <iostream> using namespace std; // Function to find X void Find_X( int A, int B) { // Code for implementing the approach int g = std::min(A, B - 1); if (g == 0) { std::cout << g << std::endl; } else { int i = (A - g) % B; int j = (g / 2) + (g % 2); std::cout << j + i / 2 << std::endl; } } // Driver function int main() { // Inputs int A = 4; int B = 7; // Function call Find_X(A, B); return 0; } // code is contributed by shinjanpatra |
Java
// Java code to implement the approach import java.util.*; // Driver Class public class Main { // Driver Function public static void main(String[] args) { // Inputs int A = 4 ; int B = 7 ; // Function call Find_X(A, B); } // Method to print appropriate value of X public static void Find_X( int A, int B) { // Code for implementing approach int g = Math.min(A, B - 1 ); if (g == 0 ) { System.out.println(g); } else { int i = (A - g) % B; int j = (g / 2 ) + (g % 2 ); System.out.println(j + i / 2 ); } } } |
Python3
# Python program for the above approach def find_X(A, B): # Code for implementing the approach g = min (A, B - 1 ) if g = = 0 : print (g) else : i = (A - g) % B j = (g / / 2 ) + (g % 2 ) print (j + i / / 2 ) # Driver function if __name__ = = "__main__" : # Inputs A = 4 B = 7 # Function call find_X(A, B) # This code is contributed by Susobhan Akhuli |
C#
// C# program for the above approach using System; public class GFG { // Function to find X static void Find_X( int A, int B) { // Code for implementing the approach int g = Math.Min(A, B - 1); if (g == 0) { Console.WriteLine(g); } else { int i = (A - g) % B; int j = (g / 2) + (g % 2); Console.WriteLine(j + i / 2); } } // Driver function static void Main() { // Inputs int A = 4; int B = 7; // Function call Find_X(A, B); // Keep the console window open Console.ReadLine(); } } // This code is contributed by Susobhan Akhuli |
Javascript
// JavaScript code for the above approach: // Function to find appropriate value of X function findX(A, B) { // Code for implementing the approach let g = Math.min(A, B - 1); if (g === 0) { console.log(g); } else { let i = (A - g) % B; let j = Math.floor(g / 2) + (g % 2); console.log(j + Math.floor(i / 2)); } } // Driver Function // Inputs let A = 4; let B = 7; // Function call findX(A, B); |
2
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us