Given three non-zero digits 0 < A, B, C < 9. The task is to find the smallest number divisible by 3 all of whose digits are in set {A, B, C}.
Note: It is not necessary to include all three digits. The result can be A, AA, AB, CCA etc.
Examples:
Input: A = 2, B = 4, C = 7
Output: 24
24 is the minimum number divisible by 3 that can be formed by the given digits.
Input: A = 1, B = 2, C = 3
Output: 3
Approach: Take all three numbers in an array and sort them in increasing order. Now check if any number is divisible by 3, if yes then the number will be the answer.
If not then again check if by taking any of two numbers. Finally take smallest number and our result is this number repeated three times.
Why can’t we get answer of length more than three digits?
Even if any number is not divisible by 3, repeating the smallest number 3 times will make it divisible by 3. Note that a number is divisible by 3 if sum of its digits is divisible by 3.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the minimum number// divisible by 3 formed by the given digitsint printSmallest(int a[3]){ int sum, sum1; // Sort the given array in ascending sort(a, a + 3); int i, j, k, num; // Check if any single digit is divisible by 3 for (int i = 0; i < 3; i++) { if (a[i] % 3 == 0) return a[i]; } // Check if any two digit number formed by // the given digits is divisible by 3 // starting from the minimum for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { // Generate the two digit number num = (a[i] * 10) + a[j]; if (num % 3 == 0) return num; } } // If none of the above is true, we can // form three digit number by taking a[0] // three times. return a[0]*100 + a[0]*10 + a[0];}// Driver codeint main(){ int arr[] = { 7, 7, 1 }; cout << printSmallest(arr); return 0;} |
Java
// Java implementation of the approachimport java.util.Arrays;public class GFG {// Function to return the minimum number// divisible by 3 formed by the given digits static int printSmallest(int a[]) { int sum, sum1; // Sort the given array in ascending Arrays.sort(a); int i, j, k, num; // Check if any single digit is divisible by 3 for (i = 0; i < 3; i++) { if (a[i] % 3 == 0) { return a[i]; } } // Check if any two digit number formed by // the given digits is divisible by 3 // starting from the minimum for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { // Generate the two digit number num = (a[i] * 10) + a[j]; if (num % 3 == 0) { return num; } } } // If none of the above is true, we can // form three digit number by taking a[0] // three times. return a[0] * 100 + a[0] * 10 + a[0]; }// Driver code public static void main(String[] args) { int arr[] = {7, 7, 1}; System.out.println(printSmallest(arr)); }}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach# Function to return the minimum # number divisible by 3 formed by # the given digitsdef printSmallest(a, n): sum0, sum1 = 0, 0 # Sort the given array in ascending a = sorted(a) # Check if any single digit is # divisible by 3 for i in range(n): if (a[i] % 3 == 0): return a[i] # Check if any two digit number # formed by the given digits is # divisible by 3 starting from # the minimum for i in range(n): for j in range(n): # Generate the two digit number num = (a[i] * 10) + a[j] if (num % 3 == 0): return num # If none of the above is true, we can # form three digit number by taking a[0] # three times. return a[0] * 100 + a[0] * 10 + a[0]# Driver codearr = [7, 7, 1 ]n = len(arr)print(printSmallest(arr, n))# This code is contributed# by mohit kumar 29 |
C#
// C# implementation of the approachusing System;public class GFG { // Function to return the minimum number// divisible by 3 formed by the given digits static int printSmallest(int []a) { // Sort the given array in ascending Array.Sort(a); int i, j, num; // Check if any single digit is divisible by 3 for (i = 0; i < 3; i++) { if (a[i] % 3 == 0) { return a[i]; } } // Check if any two digit number formed by // the given digits is divisible by 3 // starting from the minimum for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { // Generate the two digit number num = (a[i] * 10) + a[j]; if (num % 3 == 0) { return num; } } } // If none of the above is true, we can // form three digit number by taking a[0] // three times. return a[0] * 100 + a[0] * 10 + a[0]; } // Driver code public static void Main() { int []arr = {7, 7, 1}; Console.Write(printSmallest(arr)); }}//This code is contributed by Rajput-Ji |
PHP
<?php// PHP implementation of the approach // Function to return the minimum number // divisible by 3 formed by the given digits function printSmallest($a){ // Sort the given array in ascending sort($a); // Check if any single digit // is divisible by 3 for ($i = 0; $i < 3; $i++) { if ($a[$i] % 3 == 0) return $a[$i]; } // Check if any two digit number formed // by the given digits is divisible by 3 // starting from the minimum for ($i = 0; $i < 3; $i++) { for ($j = 0; $j < 3; $j++) { // Generate the two digit number $num = ($a[$i] * 10) + $a[$j]; if ($num % 3 == 0) return $num; } } // If none of the above is true, we can // form three digit number by taking a[0] // three times. return $a[0] * 100 + $a[0] * 10 + $a[0]; } // Driver code $arr = array( 7, 7, 1 );echo printSmallest($arr);// This code is contributed by Ryuga?> |
Javascript
<script> // JavaScript implementation of the approach // Function to return the minimum number // divisible by 3 formed by the given digits function printSmallest(a) { // Sort the given array in ascending a.sort(function(a, b){return a - b}); let i, j, num; // Check if any single digit is divisible by 3 for (i = 0; i < 3; i++) { if (a[i] % 3 == 0) { return a[i]; } } // Check if any two digit number formed by // the given digits is divisible by 3 // starting from the minimum for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { // Generate the two digit number num = (a[i] * 10) + a[j]; if (num % 3 == 0) { return num; } } } // If none of the above is true, we can // form three digit number by taking a[0] // three times. return a[0] * 100 + a[0] * 10 + a[0]; } let arr = [7, 7, 1]; document.write(printSmallest(arr));</script> |
Output:
111
Time Complexity: O(1)
Auxiliary Space: 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!
