Given a set of ‘N’ digits. The task is to find the maximum integer that we can make from these digits. The resultant number must be divisible by 2, 3, and 5.
Note: It is not necessary to use all the digits from the set. Also, leading zeroes are not allowed.
Examples:
Input: N = 11, setOfDigits = {3, 4, 5, 4, 5, 3, 5, 3, 4, 4, 0}
Output: 5554443330
After arranging all the elements in a non-increasing order as 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 0. The sum of all the digit is 40. Thus when we found out that the remainder of 40, when divided by 3, is 1. Then we’ll start traversing from the end to the start and if we encounter any digit with the same remainder, which we got 4 at the position 7 will be erased it. Now the sum is 36 which is divisible 3 and the new largest number will be 5554443330, which is divisible by 2, 3, and 5.
Input: N = 1, setOfDigits = {0}
Output: 0
Approach: Below is the step by step algorithm to solve this problem:
- Initialize the set of digits in a vector.
- Any number is divisible by 2, 3 and 5 only if the sum of digits is divisible by 3 and the last digit is 0.
- Check if 0 is not present in the vector, then it is not possible to create a number because it will not be divisible by 5.
- Sort the vector in a non-increasing manner if the first element is 0 after that, then print 0.
- Find the modulus of sum of all the digits by 3 and if it’s 1 then delete the first element with the same remainder while traversing from the end.
- If there is no element with the same remainder, then delete two elements which has a remainder as 3 – y.
- Print all the remaining digits of a vector as a single integer.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;#define ll long long// Function to find the largest// integer with the given setint findLargest(int n, vector<int>& v){ int flag = 0; ll sum = 0; // find sum of all the digits // look if any 0 is present or not for (int i = 0; i < n; i++) { if (v[i] == 0) flag = 1; sum += v[i]; } // if 0 is not present, the resultant number // won't be divisible by 5 if (!flag) cout << "Not possible" << endl; else { // sort all the elements in a non-decreasing manner sort(v.begin(), v.end(), greater<int>()); // if there is just one element 0 if (v[0] == 0) { cout << "0" << endl; return 0; } else { int flag = 0; // find the remainder of the sum // of digits when divided by 3 int y = sum % 3; // there can a remainder as 1 or 2 if (y != 0) { // traverse from the end of the digits for (int i = n - 1; i >= 0; i--) { // first element which has the same remainder // remove it if (v[i] % 3 == y) { v.erase(v.begin() + i); flag = 1; break; } } // if there is no element which // has a same remainder as y if (flag == 0) { // subtract it by 3 ( could be one or two) y = 3 - y; int cnt = 0; for (int i = n - 1; i >= 0; i--) { // delete two minimal digits // which has a remainder as y if (v[i] % 3 == y) { v.erase(v.begin() + i); cnt++; if (cnt >= 2) break; } } } } if (*v.begin() == 0) cout << "0" << endl; // print all the digits as a single integer else for (int i : v) { cout << i; } } }}// Driver codeint main(){ // initialize the number of set of digits int n = 11; // initialize all the set of digits in a vector vector<int> v{ 3, 9, 9, 6, 4, 3, 6, 4, 9, 6, 0 }; findLargest(n, v); return 0;} |
Java
// Java implementation of above approachimport java.util.*;class GFG { // Function to find the largest // integer with the given set static int findLargest(int n, Vector<Integer> v) { int flag = 0; long sum = 0; // find sum of all the digits // look if any 0 is present or not for (int i = 0; i < n; i++) { if (v.get(i) == 0) flag = 1; sum += v.get(i); } // if 0 is not present, the resultant number // won't be divisible by 5 if (flag != 1) System.out.println("Not possible"); else { // sort all the elements in a non-decreasing manner Collections.sort(v, Collections.reverseOrder()); // if there is just one element 0 if (v.get(0) == 0) { System.out.println("0"); return 0; } else { int flags = 0; // find the remainder of the sum // of digits when divided by 3 int y = (int)(sum % 3); // there can a remainder as 1 or 2 if (y != 0) { // traverse from the end of the digits for (int i = n - 1; i >= 0; i--) { // first element which has the same remainder // remove it if (v.get(i) % 3 == y) { v.remove(i); flags = 1; break; } } // if there is no element which // has a same remainder as y if (flags == 0) { // subtract it by 3 ( could be one or two) y = 3 - y; int cnt = 0; for (int i = n - 1; i >= 0; i--) { // delete two minimal digits // which has a remainder as y if (v.get(i) % 3 == y) { v.remove(i); cnt++; if (cnt >= 2) break; } } } } if (v.get(0) == 0) System.out.println("0"); // print all the digits as a single integer else for (Integer i : v) { System.out.print(i); } } } return Integer.MIN_VALUE; } // Driver code public static void main(String[] args) { // initialize the number of set of digits int arr[] = { 3, 9, 9, 6, 4, 3, 6, 4, 9, 6, 0 }; int n = 11; Vector<Integer> v = new Vector<Integer>(); // initialize all the set of digits in a vector for (int i = 0; i < n; i++) v.add(i, arr[i]); findLargest(n, v); }}// This code contributed by Rajput-Ji |
Python3
# Python 3 implementation of above approach# Function to find the largest# integer with the given setdef findLargest(n, v): flag = 0 sum = 0 # find sum of all the digits # look if any 0 is present or not for i in range(n): if (v[i] == 0): flag = 1 sum += v[i] # if 0 is not present, the resultant number # won't be divisible by 5 if (flag == 0): print("Not possible") else: # sort all the elements in a # non-decreasing manner v.sort(reverse = True) # if there is just one element 0 if (v[0] == 0): print("0") return 0 else: flag = 0 # find the remainder of the sum # of digits when divided by 3 y = sum % 3 # there can a remainder as 1 or 2 if (y != 0): # traverse from the end of the digits i = n - 1 while(i >= 0): # first element which has the same # remainder, remove it if (v[i] % 3 == y): v.remove(v[i]) flag = 1 break i -= 1 # if there is no element which # has a same remainder as y if (flag == 0): # subtract it by 3 ( could be one or two) y = 3 - y cnt = 0 i = n - 1 while(i >= 0): # delete two minimal digits # which has a remainder as y if (v[i] % 3 == y): v.remove(v[i]) cnt += 1 if (cnt >= 2): break i -= 1 # print all the digits as a single integer for i in (v): print(i, end = "") # Driver codeif __name__ == '__main__': # initialize the number of set of digits n = 11 # initialize all the set of # digits in a vector v = [3, 9, 9, 6, 4, 3, 6, 4, 9, 6, 0] findLargest(n, v) # This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the above approachusing System;using System.Collections;class GFG { // Function to find the largest // integer with the given set static int findLargest(int n, ArrayList v) { int flag = 0; long sum = 0; // find sum of all the digits // look if any 0 is present or not for (int i = 0; i < n; i++) { if ((int)v[i] == 0) flag = 1; sum += (int)v[i]; } // if 0 is not present, the resultant number // won't be divisible by 5 if (flag != 1) Console.WriteLine("Not possible"); else { // sort all the elements in a non-decreasing manner v.Sort(); v.Reverse(); // if there is just one element 0 if ((int)v[0] == 0) { Console.WriteLine("0"); return 0; } else { int flags = 0; // find the remainder of the sum // of digits when divided by 3 int y = (int)(sum % 3); // there can a remainder as 1 or 2 if (y != 0) { // traverse from the end of the digits for (int i = n - 1; i >= 0; i--) { // first element which has the same remainder // remove it if ((int)v[i] % 3 == y) { v.RemoveAt(i); flags = 1; break; } } // if there is no element which // has a same remainder as y if (flags == 0) { // subtract it by 3 ( could be one or two) y = 3 - y; int cnt = 0; for (int i = n - 1; i >= 0; i--) { // delete two minimal digits // which has a remainder as y if ((int)v[i] % 3 == y) { v.RemoveAt(i); cnt++; if (cnt >= 2) break; } } } } if ((int)v[0] == 0) Console.WriteLine("0"); // print all the digits as a single integer else for (int i = 0; i < v.Count; i++) { Console.Write(v[i]); } } } return int.MinValue; } // Driver code static void Main() { // initialize the number of set of digits int[] arr = { 3, 9, 9, 6, 4, 3, 6, 4, 9, 6, 0 }; int n = 11; ArrayList v = new ArrayList(); // initialize all the set of digits in a vector for (int i = 0; i < n; i++) v.Add(arr[i]); findLargest(n, v); }}// This code contributed by mits |
Javascript
<script>// JavaScript implementation of above approach// Function to find the largest// integer with the given setfunction findLargest(n,v){ let flag = 0; let sum = 0; // find sum of all the digits // look if any 0 is present or not for (let i = 0; i <n; i++) { if (v[i] == 0) flag = 1; sum += v[i]; } // if 0 is not present, the resultant number // won't be divisible by 5 if (!flag) document.write("Not possible","</br>"); else { // sort all the elements in a non-decreasing manner v.sort((a,b)=>b-a); // if there is just one element 0 if (v[0] == 0) { document.write("0","</br>"); return 0; } else { let flag = 0; // find the remainder of the sum // of digits when divided by 3 let y = sum % 3; // there can a remainder as 1 or 2 if (y != 0) { // traverse from the end of the digits for (let i = n - 1; i >= 0; i--) { // first element which has the same remainder // remove it if (v[i] % 3 == y) { v = v.splice(i,1); flag = 1; break; } } // if there is no element which // has a same remainder as y if (flag == 0) { // subtract it by 3 ( could be one or two) y = 3 - y; let cnt = 0; for (let i = n - 1; i >= 0; i--) { // delete two minimal digits // which has a remainder as y if (v[i] % 3 == y) { v.splice(i,1); cnt++; if (cnt >= 2) break; } } } } if (v[0] == 0) document.write("0","</br>"); // print all the digits as a single integer else for (let i of v) { document.write(i); } } }}// Driver code// initialize the number of set of digitslet n = 11;// initialize all the set of digits in a vectorlet v = [ 3, 9, 9, 6, 4, 3, 6, 4, 9, 6, 0 ];findLargest(n, v);// This code is contributed by shinjanpatra</script> |
Output:
999666330
Time Complexity: O(n log n)
Space Complexity: O(1)
Alternate Solution :
Below is an implementation by Keegan Fisher, Seattle, WA
C++
#include <bits/stdc++.h>using namespace std;// return a String representing the largest value that is // both a combination of the values from the parameter array // "vals" and divisible by 2, 3, and 5. string findLargest(int vals[], int N) { // sort the array in ascending order sort(vals, vals + N); string sb; // index of the lowest value divisible by 3 in "vals" // if not present, no possible value int index_div_3 = -1; // if a zero is not found, no possible value bool zero = false; // find minimum multiple of 3 and check for 0 for (int i = 0; i < N; i++) { // break when finding the first multiple of 3 // which is minimal due to sort in asc order if (vals[i] % 3 == 0 && vals[i] != 0) { index_div_3 = i; break; } if (vals[i] == 0) { zero = true; } } // if no multiple of 3 or no zero, then no value if (index_div_3 == -1 || !zero) { return sb; } // construct the output StringBuilder // adding the values to the string from highest // to lowest, not adding the val[index_div_3] // until reaching the 0s in the array, at which // point add the multiple of 3 followed by // any 0s in the array for (int i = N - 1; i >= 0; i--) { if (i != index_div_3) { if (vals[i] == 0 && index_div_3 != -1) { sb = sb + to_string(vals[index_div_3]); sb = sb + to_string(vals[i]); index_div_3 = -1; } else { sb = sb + to_string(vals[i]); } } } return sb; } int main(){ int vals[] = { 0, 0, 0, 2, 3, 4, 2, 7, 6, 9 }; int N = sizeof(vals) / sizeof(vals[0]); cout << "Output = " << findLargest(vals, N) << endl; return 0;}// This code is contributed by divyeshrabadiya07 |
Java
import java.util.Arrays;class GFG { // Driver public static void main() { int[] vals = { 0, 0, 0, 2, 3, 4, 2, 7, 6, 9 }; System.out.println("Output = " + findLargest(vals)); } // return a String representing the largest value that is // both a combination of the values from the parameter array // "vals" and divisible by 2, 3, and 5. public static String findLargest(int[] vals) { // sort the array in ascending order Arrays.sort(vals); StringBuilder sb = new StringBuilder(); // index of the lowest value divisible by 3 in "vals" // if not present, no possible value int index_div_3 = -1; // if a zero is not found, no possible value boolean zero = false; // find minimum multiple of 3 and check for 0 for (int i = 0; i < vals.length; i++) { // break when finding the first multiple of 3 // which is minimal due to sort in asc order if (vals[i] % 3 == 0 && vals[i] != 0) { index_div_3 = i; break; } if (vals[i] == 0) { zero = true; } } // if no multiple of 3 or no zero, then no value if (index_div_3 == -1 || !zero) { return sb.toString(); } // construct the output StringBuilder // adding the values to the string from highest // to lowest, not adding the val[index_div_3] // until reaching the 0s in the array, at which // point add the multiple of 3 followed by // any 0s in the array for (int i = vals.length - 1; i >= 0; i--) { if (i != index_div_3) { if (vals[i] == 0 && index_div_3 != -1) { sb.append(vals[index_div_3]); sb.append(vals[i]); index_div_3 = -1; } else { sb.append(vals[i]); } } } return sb.toString(); }} |
Python3
# Return a String representing the largest # value that is both a combination of the# values from the parameter array # "vals" and divisible by 2, 3, and 5.def findLargest (vals): # Sort the array in ascending order vals.sort() sb = "" # Index of the lowest value divisible # by 3 in "vals" if not present, no # possible value index_div_3 = -1 # If a zero is not found, no possible value zero = False # Find minimum multiple of 3 and check for 0 for i in range(len(vals)): # Break when finding the first # multiple of 3 which is minimal # due to sort in asc order if (vals[i] % 3 == 0 and vals[i] != 0): index_div_3 = i break if (vals[i] == 0): zero = True # If no multiple of 3 or no zero, then no value if (index_div_3 == -1 or zero == False): return str(sb) # Construct the output String by # adding the values to the string from highest # to lowest, not adding the val[index_div_3] # until reaching the 0s in the array, at which # point add the multiple of 3 followed by # any 0s in the array for i in range(len(vals) - 1, -1, -1): if (i != index_div_3): if (vals[i] == 0 and index_div_3 != -1): sb += str(vals[index_div_3]) sb += str(vals[i]) index_div_3 = -1 else: sb += str(vals[i]) return str(sb)# Driver codeif __name__ == '__main__': vals = [ 0, 0, 0, 2, 3, 4, 2, 7, 6, 9 ] print("Output =", findLargest(vals))# This code is contributed by himanshu77 |
C#
using System;using System.Text;class GFG { // Driver public static void Main() { int[] vals = { 0, 0, 0, 2, 3, 4, 2, 7, 6, 9 }; Console.WriteLine("Output = " + findLargest(vals)); } // return a String representing the largest value that is // both a combination of the values from the parameter array // "vals" and divisible by 2, 3, and 5. public static string findLargest(int[] vals) { // sort the array in ascending order Array.Sort(vals); StringBuilder sb = new StringBuilder(); // index of the lowest value divisible by 3 in "vals" // if not present, no possible value int index_div_3 = -1; // if a zero is not found, no possible value bool zero = false; // find minimum multiple of 3 and check for 0 for (int i = 0; i < vals.Length; i++) { // break when finding the first multiple of 3 // which is minimal due to sort in asc order if (vals[i] % 3 == 0 && vals[i] != 0) { index_div_3 = i; break; } if (vals[i] == 0) { zero = true; } } // if no multiple of 3 or no zero, then no value if (index_div_3 == -1 || !zero) { return sb.ToString(); } // construct the output StringBuilder // adding the values to the string from highest // to lowest, not adding the val[index_div_3] // until reaching the 0s in the array, at which // point add the multiple of 3 followed by // any 0s in the array for (int i = vals.Length - 1; i >= 0; i--) { if (i != index_div_3) { if (vals[i] == 0 && index_div_3 != -1) { sb.Append(vals[index_div_3]); sb.Append(vals[i]); index_div_3 = -1; } else { sb.Append(vals[i]); } } } return sb.ToString(); }}// This code is contributed by SoumikMondal |
Javascript
<script>// Return a String representing the largest // value that is both a combination of the// values from the parameter array // "vals" and divisible by 2, 3, and 5.function findLargest (vals){ // Sort the array in ascending order vals.sort() let sb = "" // Index of the lowest value divisible // by 3 in "vals" if not present, no // possible value let index_div_3 = -1 // If a zero is not found, no possible value let zero = false // Find minimum multiple of 3 and check for 0 for(let i=0;i<vals.length;i++){ // Break when finding the first // multiple of 3 which is minimal // due to sort in asc order if (vals[i] % 3 == 0 && vals[i] != 0){ index_div_3 = i break } if (vals[i] == 0) zero = true } // If no multiple of 3 or no zero, then no value if (index_div_3 == -1 || zero == false) return sb // Construct the output String by // adding the values to the string from highest // to lowest, not adding the val[index_div_3] // until reaching the 0s in the array, at which // point add the multiple of 3 followed by // any 0s in the array for(let i=vals.length - 1;i>=0;i--){ if (i != index_div_3){ if (vals[i] == 0 && index_div_3 != -1){ sb += parseInt(vals[index_div_3]) sb += parseInt(vals[i]) index_div_3 = -1 } else sb += parseInt(vals[i]) } } return sb}// Driver codelet vals = [ 0, 0, 0, 2, 3, 4, 2, 7, 6, 9 ]document.write("Output =", findLargest(vals))// This code is contributed by shinjanpatra</script> |
Output:
Output = 9764223000
Time Complexity: O(n log n)
Space Complexity: 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!
