Find Nth smallest number that is divisible by 100 exactly K times
Given two numbers N and K . The task is to find N’th smallest number that is divided by 100 exactly K times.
Examples:
Input : N = 12, K = 2
Output : 120000
120000 is divisible by 100 exactly 2 times and
is the 12 th smallest number also.
Input : N = 1000, K = 2
Output : 10010000
Approach:
- First, find the smallest number that is divisible by 100 exactly K times. That is 2*K 0’s after 1 as 100 has two 0’s only.
- To find N’th smallest number, multiply N with the previous number we get after adding 2*k 0’s.
- Consider a case when N is divisible by 100 as if we multiply N with the previous number then the new number will have more than (2*k + 1) trailing 0’s that means it will divisible by 100 more than K times.
- Multiply that number with (N + 1). Use string as N and K can be very large that will not fit in integer limit.
Below is the implementation of above approach:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to find the Nth smallest number string find_number( int N, int K) { string r; // If N is divisible by 100 then we // multiply N + 1 otherwise, it will be // divisible by 100 more than K times if (N % 100 == 0) { N += 1; // convert integer to string r = to_string(N); } // if N is not divisible by 100 else { // convert integer to string r = to_string(N); } // add 2*K 0's at the end to be divisible // by 100 exactly K times for ( int i = 1; i <= K; i++) r += "00" ; return r; } // Driver Code int main() { int N = 1000, K = 2; string ans = find_number(N, K); cout << ans << "\n" ; return 0; } |
Java
// Java implementation of above approach import java.util.*; class GFG { // Function to find the Nth smallest number static String find_number( int N, int K) { String r; // If N is divisible by 100 then we // multiply N + 1 otherwise, it will be // divisible by 100 more than K times if (N % 100 == 0 ) { N += 1 ; // convert integer to string r = String.valueOf(N); } // if N is not divisible by 100 else { // convert integer to string r = String.valueOf(N); } // add 2*K 0's at the end to be divisible // by 100 exactly K times for ( int i = 1 ; i <= K; i++) r += "00" ; return r; } // Driver Code public static void main(String[] args) { int N = 1000 , K = 2 ; String ans = find_number(N, K); System.out.println(ans); } } /* This code is contributed by PrinciRaj1992 */ |
Python3
# Python3 implementation of above approach # Function to find the Nth smallest number def find_number(N, K): r = "" # If N is divisible by 100 then we # multiply N + 1 otherwise, it will be # divisible by 100 more than K times if (N % 100 = = 0 ): N + = 1 ; # convert integer to string r = str (N) # if N is not divisible by 100 else : # convert integer to string r = str (N) # add 2*K 0's at the end to be divisible # by 100 exactly K times for i in range ( 1 , K + 1 ): r + = "00" return r # Driver Code N = 1000 K = 2 ; ans = find_number(N, K) print (ans) # This code is contributed by Mohit Kumar |
C#
// C# implementation of the approach using System; class GFG { // Function to find the Nth smallest number static String find_number( int N, int K) { String r; // If N is divisible by 100 then we // multiply N + 1 otherwise, it will be // divisible by 100 more than K times if (N % 100 == 0) { N += 1; // convert integer to string r = N.ToString(); } // if N is not divisible by 100 else { // convert integer to string r = N.ToString(); } // add 2*K 0's at the end to be divisible // by 100 exactly K times for ( int i = 1; i <= K; i++) r += "00" ; return r; } // Driver Code public static void Main(String[] args) { int N = 1000, K = 2; String ans = find_number(N, K); Console.WriteLine(ans); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation of above approach // Function to find the Nth smallest number function find_number(N, K) { var r; // If N is divisible by 100 then we // multiply N + 1 otherwise, it will be // divisible by 100 more than K times if (N % 100 == 0) { N += 1; // convert integer to string r = N.toString(); } // if N is not divisible by 100 else { // convert integer to string r = N.toString(); } // add 2*K 0's at the end to be divisible // by 100 exactly K times for ( var i = 1; i <= K; i++) r += "00" ; return r; } // Driver Code var N = 1000, K = 2; var ans = find_number(N, K); document.write(ans); // This code is contributed by Khushboogoyal499 </script> |
Output:
10010000
Time Complexity: O(K)
Auxiliary Space: O(1)
Contact Us