Given two integers L and R where L ? R, the task is to find an integer K such that:
- L ? K ? R.
- All the digits of K are distinct.
- The value of the expression (L – K) * (K – R) is maximum.
If multiple answers exist then choose the larger value for K.
Examples:
Input: L = 5, R = 10
Output: 8
Input: L = 50, R = 60
Output: 56
Approach: Iterate from L to R and for each value of K, check whether it contains all distinct digits and (L – K) * (K – R) is maximum. If two or more values give the same maximum value for the expression then choose the greater value for K.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const int MAX = 10;// Function that returns true if x// contains all distinct digitsbool distinctDigits(int x){ bool present[MAX] = { false }; while (x > 0) { // Last digit of x int digit = x % 10; // If current digit has // appeared before if (present[digit]) return false; // Mark the current digit // to present present[digit] = true; // Remove the last digit x /= 10; } return true;}// Function to return the// required value of kint findK(int l, int r){ // To store the maximum value // for the given expression int maxExp = INT_MIN; int k = -1; for (int i = l; i <= r; i++) { // If i contains all distinct digits if (distinctDigits(i)) { int exp = (l - i) * (i - r); // If the value of the expression // is also maximum then update k // and the expression if (exp >= maxExp) { k = i; maxExp = exp; } } } return k;}// Driver codeint main(){ int l = 50, r = 60; cout << findK(l, r); return 0;} |
Java
// Java implementation of the approachclass GFG{static int MAX = 10;// Function that returns true if x// contains all distinct digitsstatic boolean distinctDigits(int x){ boolean []present = new boolean[MAX]; while (x > 0) { // Last digit of x int digit = x % 10; // If current digit has // appeared before if (present[digit]) return false; // Mark the current digit // to present present[digit] = true; // Remove the last digit x /= 10; } return true;}// Function to return the// required value of kstatic int findK(int l, int r){ // To store the maximum value // for the given expression int maxExp = Integer.MIN_VALUE; int k = -1; for (int i = l; i <= r; i++) { // If i contains all distinct digits if (distinctDigits(i)) { int exp = (l - i) * (i - r); // If the value of the expression // is also maximum then update k // and the expression if (exp >= maxExp) { k = i; maxExp = exp; } } } return k;}// Driver codepublic static void main(String[] args){ int l = 50, r = 60; System.out.print(findK(l, r));}}// This code is contributed by 29AjayKumar |
Python 3
# Python3 implementation of the approachimport sysMAX = 10# Function that returns true if x# contains all distinct digitsdef distinctDigits(x): present = [False for i in range(MAX)] while (x > 0): # Last digit of x digit = x % 10 # If current digit has # appeared before if (present[digit]): return False # Mark the current digit # to present present[digit] = True # Remove the last digit x = x // 10 return True# Function to return the# required value of kdef findK(l, r): # To store the maximum value # for the given expression maxExp = -sys.maxsize - 1 k = -1 for i in range(l, r + 1, 1): # If i contains all distinct digits if (distinctDigits(i)): exp = (l - i) * (i - r) # If the value of the expression # is also maximum then update k # and the expression if (exp >= maxExp): k = i; maxExp = exp return k# Driver codeif __name__ == '__main__': l = 50 r = 60 print(findK(l, r)) # This code is contributed by Surendra_Gangwar |
C#
// C# implementation of the approachusing System;class GFG{static int MAX = 10;// Function that returns true if x// contains all distinct digitsstatic bool distinctDigits(int x){ bool []present = new bool[MAX]; while (x > 0) { // Last digit of x int digit = x % 10; // If current digit has // appeared before if (present[digit]) return false; // Mark the current digit // to present present[digit] = true; // Remove the last digit x /= 10; } return true;}// Function to return the// required value of kstatic int findK(int l, int r){ // To store the maximum value // for the given expression int maxExp = int.MinValue; int k = -1; for (int i = l; i <= r; i++) { // If i contains all distinct digits if (distinctDigits(i)) { int exp = (l - i) * (i - r); // If the value of the expression // is also maximum then update k // and the expression if (exp >= maxExp) { k = i; maxExp = exp; } } } return k;}// Driver codepublic static void Main(String[] args){ int l = 50, r = 60; Console.Write(findK(l, r));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// javascript implementation of the approach var MAX = 10; // Function that returns true if x // contains all distinct digits function distinctDigits(x) { var present = new Array(MAX).fill(false); while (x > 0) { // Last digit of x var digit = x % 10; // If current digit has // appeared before if (present[digit]) return false; // Mark the current digit // to present present[digit] = true; // Remove the last digit x = parseInt(x/10); } return true; } // Function to return the // required value of k function findK(l , r) { // To store the maximum value // for the given expression var maxExp = Number.MIN_VALUE; var k = -1; for (var i = l; i <= r; i++) { // If i contains all distinct digits if (distinctDigits(i)) { var exp = (l - i) * (i - r); // If the value of the expression // is also maximum then update k // and the expression if (exp >= maxExp) { k = i; maxExp = exp; } } } return k; } // Driver code var l = 50, r = 60; document.write(findK(l, r));// This code is contributed by gauravrajput1</script> |
Output:
56
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!
