두 개의 정수가 주어지면 에스 그리고 디 찾기 가장 작은 정확히 다음과 같은 가능한 숫자 d 자리 그리고 자릿수의 합 같음 에스 .
숫자를 다음과 같이 반환합니다. 끈 . 해당 번호가 없으면 반환 '-1' .
예:
입력: 초 = 9 일 = 2
산출: 18
설명: 18은 자릿수의 합 = 9이고 총 자릿수 = 2일 때 가능한 가장 작은 수입니다.현지 날짜입력: 초 = 20 일 = 3
산출: 299
설명: 299는 자릿수의 합 = 20이고 총 자릿수 = 3일 때 가능한 가장 작은 수입니다.입력: 초 = 1 일 = 1
산출: 1
설명: 1은 자릿수의 합 = 1이고 총 자릿수 = 1일 때 가능한 가장 작은 수입니다.
알파벳과 숫자
목차
[무차별 접근 방식] 순차적으로 반복 - O(d*(10^d)) 시간 및 O(1) 공간
C++숫자는 순차적이므로 무차별적인 접근 방식 에서 반복 가장 작은 d 자리 숫자 가장 큰 하나하나 확인 중. 모든 숫자에 대해 우리는 다음을 계산합니다. 그 자릿수의 합 가능한 가장 작은 숫자가 선택되도록 첫 번째 유효한 일치 항목을 반환합니다. 유효한 숫자가 없으면 반환됩니다. '-1' .
// C++ program to find the smallest d-digit // number with the given sum using // a brute force approach #include
// Java program to find the smallest d-digit // number with the given sum using // a brute force approach import java.util.*; class GfG { static String smallestNumber(int s int d) { // The smallest d-digit number is 10^(d-1) int start = (int) Math.pow(10 d - 1); // The largest d-digit number is 10^d - 1 int end = (int) Math.pow(10 d) - 1; // Iterate through all d-digit numbers for (int num = start; num <= end; num++) { int sum = 0 x = num; // Calculate sum of digits while (x > 0) { sum += x % 10; x /= 10; } // If sum matches return the number // as a string if (sum == s) { return Integer.toString(num); } } // If no valid number is found return '-1' return '-1'; } // Driver Code public static void main(String[] args) { int s = 9 d = 2; System.out.println(smallestNumber(s d)); } }
# Python program to find the smallest d-digit # number with the given sum using # a brute force approach def smallestNumber(s d): # The smallest d-digit number is 10^(d-1) start = 10**(d - 1) # The largest d-digit number is 10^d - 1 end = 10**d - 1 # Iterate through all d-digit numbers for num in range(start end + 1): sum_digits = 0 x = num # Calculate sum of digits while x > 0: sum_digits += x % 10 x //= 10 # If sum matches return the number # as a string if sum_digits == s: return str(num) # If no valid number is found return '-1' return '-1' # Driver Code if __name__ == '__main__': s d = 9 2 print(smallestNumber(s d))
// C# program to find the smallest d-digit // number with the given sum using // a brute force approach using System; class GfG { static string smallestNumber(int s int d) { // The smallest d-digit number is 10^(d-1) int start = (int)Math.Pow(10 d - 1); // The largest d-digit number is 10^d - 1 int end = (int)Math.Pow(10 d) - 1; // Iterate through all d-digit numbers for (int num = start; num <= end; num++) { int sum = 0 x = num; // Calculate sum of digits while (x > 0) { sum += x % 10; x /= 10; } // If sum matches return the number // as a string if (sum == s) { return num.ToString(); } } // If no valid number is found return '-1' return '-1'; } // Driver Code public static void Main() { int s = 9 d = 2; Console.WriteLine(smallestNumber(s d)); } }
// JavaScript program to find the smallest d-digit // number with the given sum using // a brute force approach function smallestNumber(s d) { // The smallest d-digit number is 10^(d-1) let start = Math.pow(10 d - 1); // The largest d-digit number is 10^d - 1 let end = Math.pow(10 d) - 1; // Iterate through all d-digit numbers for (let num = start; num <= end; num++) { let sum = 0 x = num; // Calculate sum of digits while (x > 0) { sum += x % 10; x = Math.floor(x / 10); } // If sum matches return the number // as a string if (sum === s) { return num.toString(); } } // If no valid number is found return '-1' return '-1'; } // Driver Code let s = 9 d = 2; console.log(smallestNumber(s d));
산출
18
[예상 접근 방식] 그리디(Greedy) 기법 활용 - O(d) 시간과 O(1) 공간
이 접근 방식은 가장 왼쪽 숫자를 보장합니다. 0이 아니다 그래서 우리는 예비 1 이를 위해 나머지 금액을 분배합니다. 오른쪽에서 왼쪽으로 가능한 가장 작은 수를 형성합니다. 그만큼 탐욕스러운 접근 가능한 가장 큰 값(최대 9)을 배치하는 데 도움이 됩니다. 가장 오른쪽 위치 숫자를 작게 유지하기 위해.
디스플레이 크기를 아는 방법
위의 아이디어를 구현하는 단계:
- 제약 조건을 확인하여 유효한 합계 사용하여 형성할 수 있다 d 자리 그렇지 않으면 반환 '-1' .
- 초기화 결과 문자열로 d '0's 그리고 예비 1 위해 가장 왼쪽 숫자 감소시킴으로써 초는 1 .
- 에서 트래버스 오른쪽에서 왼쪽으로 그리고 배치 가능한 가장 큰 숫자(<= 9) 업데이트하는 동안 에스 따라서.
- 만약에 에스<= 9 현재 위치에 값을 놓고 설정합니다. 초 = 0 추가 업데이트를 중지합니다.
- 할당 가장 왼쪽 숫자 을 추가하여 남은 초 남아 있는지 확인하기 위해 0이 아닌 .
- 변환하다 결과 문자열을 필요한 형식으로 변환하고 반품 최종 출력으로 사용됩니다.
// C++ program to find the smallest d-digit // number with the given sum using // Greedy Technique #include
// Java program to find the smallest d-digit // number with the given sum using // Greedy Technique import java.util.*; class GfG { static String smallestNumber(int s int d) { // If sum is too small or too large // for d digits if (s < 1 || s > 9 * d) { return '-1'; } char[] result = new char[d]; Arrays.fill(result '0'); // Reserve 1 for the leftmost digit s--; // Fill digits from right to left for (int i = d - 1; i > 0; i--) { // Place the largest possible value <= 9 if (s > 9) { result[i] = '9'; s -= 9; } else { result[i] = (char) ('0' + s); s = 0; } } // Place the leftmost digit ensuring // it's non-zero result[0] = (char) ('1' + s); return new String(result); } // Driver Code public static void main(String[] args) { int s = 9 d = 2; System.out.println(smallestNumber(s d)); } }
# Python program to find the smallest d-digit # number with the given sum using # Greedy Technique def smallestNumber(s d): # If sum is too small or too large # for d digits if s < 1 or s > 9 * d: return '-1' result = ['0'] * d # Reserve 1 for the leftmost digit s -= 1 # Fill digits from right to left for i in range(d - 1 0 -1): # Place the largest possible value <= 9 if s > 9: result[i] = '9' s -= 9 else: result[i] = str(s) s = 0 # Place the leftmost digit ensuring # it's non-zero result[0] = str(1 + s) return ''.join(result) # Driver Code if __name__ == '__main__': s d = 9 2 print(smallestNumber(s d))
// C# program to find the smallest d-digit // number with the given sum using // Greedy Technique using System; class GfG { static string smallestNumber(int s int d) { // If sum is too small or too large // for d digits if (s < 1 || s > 9 * d) { return '-1'; } char[] result = new char[d]; Array.Fill(result '0'); // Reserve 1 for the leftmost digit s--; // Fill digits from right to left for (int i = d - 1; i > 0; i--) { // Place the largest possible value <= 9 if (s > 9) { result[i] = '9'; s -= 9; } else { result[i] = (char) ('0' + s); s = 0; } } // Place the leftmost digit ensuring // it's non-zero result[0] = (char) ('1' + s); return new string(result); } // Driver Code static void Main() { int s = 9 d = 2; Console.WriteLine(smallestNumber(s d)); } }
// JavaScript program to find the smallest d-digit // number with the given sum using // Greedy Technique function smallestNumber(s d) { // If sum is too small or too large // for d digits if (s < 1 || s > 9 * d) { return '-1'; } let result = Array(d).fill('0'); // Reserve 1 for the leftmost digit s--; // Fill digits from right to left for (let i = d - 1; i > 0; i--) { // Place the largest possible value <= 9 if (s > 9) { result[i] = '9'; s -= 9; } else { result[i] = String(s); s = 0; } } // Place the leftmost digit ensuring // it's non-zero result[0] = String(1 + s); return result.join(''); } // Driver Code let s = 9 d = 2; console.log(smallestNumber(s d));
산출
18