Given an array arr[] of size N and 2 integers K and M the task is to find the largest integer of K digits from the array arr[] which is divisible by M. Print -1 if it is impossible to find any such integer.
Note: The value of K is such that the found integer is always less than or equal to INT_MAX.
Examples:
Input: arr[] = {1, 2, 3, 4, 5, 6}, N=6, K=3, M=4
Output: 652
Explanation: The largest of 3 digits is formed by the digits 6, 5, 2 with their indices 1. 4, and 5.Input: arr[] = {4, 5, 4}, N=3, K=3, M=50
Output: -1
Explanation :- There exists no integer from the array which is divisible by 50 as there is no 0.
Naive Approach: This can be done by finding all sub-sequences of size K and then checking the condition to find the largest one.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The idea is to check every number in multiple of M in the array that if it is possible to form that number or not. If it is possible, then update the answer. Follow the steps below to solve the problem:
- If K is greater than N, then print -1 and return.
- Initialize the vector freq[] of size 10 with value 0 to store the frequency of all elements of the array arr[].
- Iterate over the range [0, N) and store the frequency of every element in the array freq[].
- Sort the array arr[] in ascending order.
- Initialize the variable X and set its value as the largest K digits from the array arr[] as the largest number possible.
- If X is less than M then print -1 and return.
- Initialize the variable answer as -1 to store the answer.
- Iterate over the range [M, X] using the variable i and perform the following steps:
- Initialize the variable y as i.
- Initialize the vector v[] of size 10 with value 0 to store the frequency of all digits of the number y.
- Traverse the vectors freq[] and v[] and if for all the positions freq[j] is greater than equal to v[j], then update the answer as the maximum of answer or y.
- After performing the above steps, print the variable answer as the answer.
Below is the implementation of the above approach.
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the largest integer// of K digits divisible by Mvoid find(vector<int>& arr, int N, int K, int M){ // Base Case, as there is no sub-sequence // of size greater than N is possible if (K > N) { cout << "-1\n"; return; } // Vector to store the frequency of each // number from the array vector<int> freq(10, 0); // Calculate the frequency of each from // the array for (int i = 0; i < N; i++) { freq[arr[i]]++; } // Sort the array in ascending order sort(arr.begin(), arr.end()); // Variable to store the maximum number // possible int X = 0; // Traverse and store the largest K digits for (int i = N - 1; K > 0; i--) { X = X * 10 + arr[i]; K--; } // Base Case if (X < M) { cout << "-1\n"; return; } // Variable to store the answer int answer = -1; // Traverse and check for each number for (int i = M; i <= X; i = i + M) { int y = i; vector<int> v(10, 0); // Calculate the frequency of each number while (y > 0) { v[y % 10]++; y = y / 10; } bool flag = true; // If frequency of any digit in y is less than // that in freq[], then it's not possible. for (int j = 0; j <= 9; j++) { if (v[j] > freq[j]) { flag = false; break; } } if (flag) answer = max(answer, i); } // Print the answer cout << answer << endl;}// Driver Codeint main(){ vector<int> arr = { 1, 2, 3, 4, 5, 6 }; int N = 6, K = 3, M = 4; find(arr, N, K, M); return 0;} |
Java
// Java code for the above approachimport java.io.*;import java.util.Arrays;;class GFG{ // Function to find the largest integer // of K digits divisible by M static void find(int[] arr, int N, int K, int M) { // Base Case, as there is no sub-sequence // of size greater than N is possible if (K > N) { System.out.println("-1\n"); return; } // Vector to store the frequency of each // number from the array int freq[] = new int[10]; // Calculate the frequency of each from // the array for (int i = 0; i < N; i++) { freq[arr[i]]++; } // Sort the array in ascending order Arrays.sort(arr); // Variable to store the maximum number // possible int X = 0; // Traverse and store the largest K digits for (int i = N - 1; K > 0; i--) { X = X * 10 + arr[i]; K--; } // Base Case if (X < M) { System.out.println("-1"); return; } // Variable to store the answer int answer = -1; // Traverse and check for each number for (int i = M; i <= X; i = i + M) { int y = i; int v[] = new int[10]; // Calculate the frequency of each number while (y > 0) { v[y % 10]++; y = y / 10; } boolean flag = true; // If frequency of any digit in y is less than // that in freq[], then it's not possible. for (int j = 0; j <= 9; j++) { if (v[j] > freq[j]) { flag = false; break; } } if (flag) answer = Math.max(answer, i); } // Print the answer System.out.println(answer); } // Driver Code public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5, 6 }; int N = 6, K = 3, M = 4; find(arr, N, K, M); }}// This code is contributed by Potta Lokesh |
Python3
# Python program for the above approach# Function to find the largest integer# of K digits divisible by Mdef find(arr, N, K, M): # Base Case, as there is no sub-sequence # of size greater than N is possible if (K > N): print("-1") return # Vector to store the frequency of each # number from the array freq = [0] * 10 # Calculate the frequency of each from # the array for i in range(N): freq[arr[i]] += 1 # Sort the array in ascending order arr.sort() # Variable to store the maximum number # possible X = 0 # Traverse and store the largest K digits for i in range(N - 1, 2, -1): X = X * 10 + arr[i] K -= 1 # Base Case if (X < M): print("-1") return # Variable to store the answer answer = -1 # Traverse and check for each number for i in range(M, X + 1, M): y = i v = [0] * 10 # Calculate the frequency of each number while (y > 0): v[y % 10] += 1 y = y // 10 flag = True # If frequency of any digit in y is less than # that in freq[], then it's not possible. for j in range(10): if (v[j] > freq[j]): flag = False break if (flag): answer = max(answer, i) # Print the answer print(answer)# Driver Codearr = [1, 2, 3, 4, 5, 6]N = 6K = 3M = 4find(arr, N, K, M)# This code is contributed by gfgking. |
C#
// C# code for the above approachusing System;public class GFG{ // Function to find the largest integer // of K digits divisible by M static void find(int[] arr, int N, int K, int M) { // Base Case, as there is no sub-sequence // of size greater than N is possible if (K > N) { Console.WriteLine("-1\n"); return; } // Vector to store the frequency of each // number from the array int []freq = new int[10]; // Calculate the frequency of each from // the array for (int i = 0; i < N; i++) { freq[arr[i]]++; } // Sort the array in ascending order Array.Sort(arr); // Variable to store the maximum number // possible int X = 0; // Traverse and store the largest K digits for (int i = N - 1; K > 0; i--) { X = X * 10 + arr[i]; K--; } // Base Case if (X < M) { Console.WriteLine("-1"); return; } // Variable to store the answer int answer = -1; // Traverse and check for each number for (int i = M; i <= X; i = i + M) { int y = i; int []v = new int[10]; // Calculate the frequency of each number while (y > 0) { v[y % 10]++; y = y / 10; } bool flag = true; // If frequency of any digit in y is less than // that in freq[], then it's not possible. for (int j = 0; j <= 9; j++) { if (v[j] > freq[j]) { flag = false; break; } } if (flag) answer = Math.Max(answer, i); } // Print the answer Console.WriteLine(answer); } // Driver Code public static void Main(string[] args) { int[] arr = { 1, 2, 3, 4, 5, 6 }; int N = 6, K = 3, M = 4; find(arr, N, K, M); }}// This code is contributed by AnkThon |
Javascript
<script>// Javascript program for the above approach// Function to find the largest integer// of K digits divisible by Mfunction find(arr, N, K, M) { // Base Case, as there is no sub-sequence // of size greater than N is possible if (K > N) { document.write("-1<br>"); return; } // Vector to store the frequency of each // number from the array let freq = new Array(10).fill(0); // Calculate the frequency of each from // the array for (let i = 0; i < N; i++) { freq[arr[i]]++; } // Sort the array in ascending order arr.sort((a, b) => a - b); // Variable to store the maximum number // possible let X = 0; // Traverse and store the largest K digits for (let i = N - 1; K > 0; i--) { X = X * 10 + arr[i]; K--; } // Base Case if (X < M) { cout << "-1\n"; return; } // Variable to store the answer let answer = -1; // Traverse and check for each number for (let i = M; i <= X; i = i + M) { let y = i; let v = new Array(10).fill(0); // Calculate the frequency of each number while (y > 0) { v[y % 10]++; y = Math.floor(y / 10); } let flag = true; // If frequency of any digit in y is less than // that in freq[], then it's not possible. for (let j = 0; j <= 9; j++) { if (v[j] > freq[j]) { flag = false; break; } } if (flag) answer = Math.max(answer, i); } // Print the answer document.write(answer);}// Driver Codelet arr = [1, 2, 3, 4, 5, 6];let N = 6, K = 3, M = 4;find(arr, N, K, M);// This code is contributed by gfgking.</script> |
Output
652
Time Complexity: O(max(M, N))
Auxiliary Space: O(1)
