Smallest number with sum of digits as N and divisible by 10^N

Find the smallest number such that the sum of its digits is N and it is divisible by 10N.

Example 1:

Input: N = 5
Outptut: 500000
Explanation: Sum of digits of 500000
is 5 and divisible by 105.

Example 2:

Input: N = 20
Output: 29900000000000000000000
Explanation: Sum of digits of 
29900000000000000000000 is 20 and
divisible by 1020.


method : greedy approach


c++ implementation:

	string digitsNum(int n)
	{
	        string r="";

	        int t=n/9;
	        int z=n-t*9;
	        
	       if(z!=0)
	       r=r+to_string(z);
	       
	       while(t--)
	       {
	           r=r+"9";
	       }
	       
	       while(n--)
	       {
	           r=r+"0";
	       }
	   return r;
	    
	}


Time Complexity: O(n) 
space Complexity: O(n) 


darkmode