Smallest integer greater than n such that it consists of digit m exactly k times
Given three integer n, m and k, the task is to find the smallest integer > n such that digit m appears exactly k times in it.
Examples:
Input: n = 111, m = 2, k = 2
Output: 122
Input: n = 111, m = 2, k = 3
Output: 222
Approach: Start iterating from n + 1 and for each integer i check whether it consists of digit m exactly k times. This way smallest integer > n with digit m occurring exactly k times can be found.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function that returns true if n contains // digit m exactly k times bool digitWell( int n, int m, int k) { int cnt = 0; while (n > 0) { if (n % 10 == m) ++cnt; n /= 10; } return cnt == k; } // Function to return the smallest integer > n // with digit m occurring exactly k times int findInt( int n, int m, int k) { int i = n + 1; while ( true ) { if (digitWell(i, m, k)) return i; i++; } } // Driver code int main() { int n = 111, m = 2, k = 2; cout << findInt(n, m, k); return 0; } |
Java
// Java implementation of the approach import java.io.*; class GFG { // Function that returns true if n contains // digit m exactly k times static boolean digitWell( int n, int m, int k) { int cnt = 0 ; while (n > 0 ) { if (n % 10 == m) ++cnt; n /= 10 ; } return cnt == k; } // Function to return the smallest integer > n // with digit m occurring exactly k times static int findInt( int n, int m, int k) { int i = n + 1 ; while ( true ) { if (digitWell(i, m, k)) return i; i++; } } // Driver code public static void main(String[] args) { int n = 111 , m = 2 , k = 2 ; System.out.println(findInt(n, m, k)); } } // This code is contributed by Code_Mech |
Python3
# Python3 implementation of the approach # Function that returns true if n # contains digit m exactly k times def digitWell(n, m, k): cnt = 0 while (n > 0 ): if (n % 10 = = m): cnt = cnt + 1 ; n = ( int )(n / 10 ); return cnt = = k; # Function to return the smallest integer > n # with digit m occurring exactly k times def findInt(n, m, k): i = n + 1 ; while ( True ): if (digitWell(i, m, k)): return i; i = i + 1 ; # Driver code n = 111 ; m = 2 ; k = 2 ; print (findInt(n, m, k)); # This code is contributed # by Akanksha Rai |
C#
// C# implementation of the approach using System; class GFG { // Function that returns true if n contains // digit m exactly k times static bool digitWell( int n, int m, int k) { int cnt = 0; while (n > 0) { if (n % 10 == m) ++cnt; n /= 10; } return cnt == k; } // Function to return the smallest integer > n // with digit m occurring exactly k times static int findInt( int n, int m, int k) { int i = n + 1; while ( true ) { if (digitWell(i, m, k)) return i; i++; } } // Driver code public static void Main() { int n = 111, m = 2, k = 2; Console.WriteLine(findInt(n, m, k)); } } // This code is contributed // by Akanksha Rai |
PHP
<?php // PHP implementation of the approach // Function that returns true if n // contains digit m exactly k times function digitWell( $n , $m , $k ) { $cnt = 0; while ( $n > 0) { if ( $n % 10 == $m ) ++ $cnt ; $n = floor ( $n / 10); } return $cnt == $k ; } // Function to return the smallest integer > n // with digit m occurring exactly k times function findInt( $n , $m , $k ) { $i = $n + 1; while (true) { if (digitWell( $i , $m , $k )) return $i ; $i ++; } } // Driver code $n = 111; $m = 2; $k = 2; echo findInt( $n , $m , $k ); // This code is contributed by Ryuga ?> |
Javascript
<script> // Javascript implementation of the approach // Function that returns true if n contains // digit m exactly k times function digitWell(n, m, k) { var cnt = 0; while (n > 0) { if (n % 10 == m) ++cnt; n = Math.floor(n/10); } if (cnt == k) return true ; else return false ; } // Function to return the smallest integer > n // with digit m occurring exactly k times function findInt(n, m, k) { var i = n + 1; while ( true ) { if (digitWell(i, m, k)) return i; i++; } } // Driver code var n = 111, m = 2, k = 2; document.write(findInt(n, m, k)); </script> |
Output:
122
Time Complexity: O(n * log10n)
Auxiliary Space: O(1), since no extra space has been taken.
Contact Us