Largest number divisible by 50 that can be formed from a given set of N digits consisting of 0s and 7s only
Given an array arr[] consisting of N integers which are either 0 or 7, the task is to find the largest number that can be formed using the array elements such that it is divisible by 50.
Examples:
Input: arr[] = {7, 7, 7, 7, 7, 7, 0, 0, 0, 0, 0, 0, 0}
Output: 777770000000Input: arr[] = {7, 0}
Output: 0
Naive Approach: The simplest approach to solve this problem is based on the following observations:
- Visualizing 50 to be equal to 5 * 10, therefore any trailing zeros inserted will be divided by 10 present as a factor of 50. Therefore, the task reduces to combining 7s such that they are divisible by 5 and for a number to be divisible by 5, its unit place should either be 0 or 5.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to calculate the frequency of 7s and 0s present in the array and generate the required number which is divisible by 50. Follow the steps below to solve the problem:
- Count the number of 7s and 0s present in the array.
- Calculate the nearest factor of 5 to the count of 7s present in the array (as 35 is the smallest factor 5 which can be obtained using 7s only)
- Display the calculated number of 7’s.
- Append trailing zeros to the number made above.
Corner Cases To be Considered:
- If the count of 0s the array is 0(then, the task is to check if the count of 7s in the array is divisible by 50 or not.
- If the count of 7s is less than 5 and no 0 is present in the array, simply print “Not Possible”.
- If the count of 7s is less than 5 and 0 is present, simply print ‘0‘.
Below is the implementation of the above approach:
C++
// C++ Program for the above approach #include <bits/stdc++.h> using namespace std; // Print the largest number divisible by 50 void printLargestDivisible( int arr[], int N) { int i, count0 = 0, count7 = 0; for (i = 0; i < N; i++) { // Counting number of 0s and 7s if (arr[i] == 0) count0++; else count7++; } // If count of 7 is divisible by 50 if (count7 % 50 == 0) { while (count7--) cout << 7; while (count0--) cout << 0; } // If count of 7 is less than 5 else if (count7 < 5) { if (count0 == 0) cout << "No" ; else cout << "0" ; } // If count of 7 is not // divisible by 50 else { // Count of groups of 5 in which // count of 7s can be grouped count7 = count7 - count7 % 5; while (count7--) cout << 7; while (count0--) cout << 0; } } // Driver Code int main() { // Given array int arr[] = { 0, 7, 0, 7, 7, 7, 7, 0, 0, 0, 0, 0, 0, 7, 7, 7 }; // Size of the array int N = sizeof (arr) / sizeof (arr[0]); printLargestDivisible(arr, N); return 0; } |
Java
// Java program of the above approach import java.io.*; class GFG { // Print the largest number divisible by 50 static void printLargestDivisible( int arr[], int N) { int i, count0 = 0 , count7 = 0 ; for (i = 0 ; i < N; i++) { // Counting number of 0s and 7s if (arr[i] == 0 ) count0++; else count7++; } // If count of 7 is divisible by 50 if (count7 % 50 == 0 ) { while (count7 != 0 ) { System.out.print( 7 ); count7 -= 1 ; } while (count0 != 0 ) { System.out.print( 0 ); count0 -= 1 ; } } // If count of 7 is less than 5 else if (count7 < 5 ) { if (count0 == 0 ) System.out.print( "No" ); else System.out.print( "0" ); } // If count of 7 is not // divisible by 50 else { // Count of groups of 5 in which // count of 7s can be grouped count7 = count7 - count7 % 5 ; while (count7 != 0 ) { System.out.print( 7 ); count7 -= 1 ; } while (count0 != 0 ) { System.out.print( 0 ); count0 -= 1 ; } } } // Driver Code public static void main(String[] args) { // Given array int arr[] = { 0 , 7 , 0 , 7 , 7 , 7 , 7 , 0 , 0 , 0 , 0 , 0 , 0 , 7 , 7 , 7 }; // Size of the array int N = arr.length; printLargestDivisible(arr, N); } } // This code is contributed by jana_sayantan. |
Python3
# Python3 Program for the above approach # Print the largest number divisible by 50 def printLargestDivisible(arr, N) : count0 = 0 ; count7 = 0 ; for i in range (N) : # Counting number of 0s and 7s if (arr[i] = = 0 ) : count0 + = 1 ; else : count7 + = 1 ; # If count of 7 is divisible by 50 if (count7 % 50 = = 0 ) : while (count7) : count7 - = 1 ; print ( 7 , end = ""); while (count0) : count0 - = 1 ; print (count0, end = ""); # If count of 7 is less than 5 elif (count7 < 5 ) : if (count0 = = 0 ) : print ( "No" , end = ""); else : print ( "0" , end = ""); # If count of 7 is not # divisible by 50 else : # Count of groups of 5 in which # count of 7s can be grouped count7 = count7 - count7 % 5 ; while (count7) : count7 - = 1 ; print ( 7 , end = ""); while (count0) : count0 - = 1 ; print ( 0 , end = ""); # Driver Code if __name__ = = "__main__" : # Given array arr = [ 0 , 7 , 0 , 7 , 7 , 7 , 7 , 0 , 0 , 0 , 0 , 0 , 0 , 7 , 7 , 7 ]; # Size of the array N = len (arr); printLargestDivisible(arr, N); # This code is contributed by AnkThon |
C#
// C# program of the above approach using System; public class GFG { // Print the largest number divisible by 50 static void printLargestDivisible( int []arr, int N) { int i, count0 = 0, count7 = 0; for (i = 0; i < N; i++) { // Counting number of 0s and 7s if (arr[i] == 0) count0++; else count7++; } // If count of 7 is divisible by 50 if (count7 % 50 == 0) { while (count7 != 0) { Console.Write(7); count7 -= 1; } while (count0 != 0) { Console.Write(0); count0 -= 1; } } // If count of 7 is less than 5 else if (count7 < 5) { if (count0 == 0) Console.Write( "No" ); else Console.Write( "0" ); } // If count of 7 is not // divisible by 50 else { // Count of groups of 5 in which // count of 7s can be grouped count7 = count7 - count7 % 5; while (count7 != 0) { Console.Write(7); count7 -= 1; } while (count0 != 0) { Console.Write(0); count0 -= 1; } } } // Driver Code public static void Main(String[] args) { // Given array int []arr = { 0, 7, 0, 7, 7, 7, 7, 0, 0, 0, 0, 0, 0, 7, 7, 7 }; // Size of the array int N = arr.Length; printLargestDivisible(arr, N); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript Program for the above approach // Print the largest number divisible by 50 function printLargestDivisible(arr, N) { var i, count0 = 0, count7 = 0; for (i = 0; i < N; i++) { // Counting number of 0s and 7s if (arr[i] == 0) count0++; else count7++; } // If count of 7 is divisible by 50 if (count7 % 50 == 0) { while (count7--) document.write(7); while (count0--) document.write(0); } // If count of 7 is less than 5 else if (count7 < 5) { if (count0 == 0) document.write( "No" ); else document.write( "0" ); } // If count of 7 is not // divisible by 50 else { // Count of groups of 5 in which // count of 7s can be grouped count7 = count7 - count7 % 5; while (count7--) document.write(7); while (count0--) document.write(0); } } // Driver Code // Given array var arr = [ 0, 7, 0, 7, 7, 7, 7, 0, 0, 0, 0, 0, 0, 7, 7, 7 ]; // Size of the array var N = arr.length; printLargestDivisible(arr, N); </script> |
Output:
7777700000000
Time Complexity: O(N)
Auxiliary Space: O(1)