logo

TechCodeview

Отпечатайте всички n-цифрени числа с нечетна и четна разлика в сумата като 1

Дадено е цяло число п представляващ броя на цифрите. Задачата е да отпечатате всички n-цифрени числа така че абсолютната разлика между сумата от цифри на четни позиции и нечетни позиции е точна 1 .
Забележка : Числото не трябва да започва с (не се допускат водещи нули).

Примери:  



Вход : n = 2
Изход : 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98

Вход : n = 3
Изход : 100, 111, 120, 122, 131, 133, 142, 144, 153, 155, 164, 166, 175, 177, 186
188, 197, 199, 210, 221, 230, 232, 241, 243, 252, 254, 263, 265, 274, 276, 285
287, 296, 298, 320, 331, 340, 342, 351, 353, 362, 364, 373, 375, 384, 386, 395
397 430 441 450 452 461 463 472 474 483 485 494 496 540 551 560
562, 571, 573, 582, 584, 593, 595, 650, 661, 670, 672, 681, 683, 692, 694, 760
771, 780, 782, 791, 793, 870, 881, 890, 892, 980, 991 следваща  

[Очакван подход] Използване на рекурсия

Идеята е да се рекурсивно генерира всички n-цифрени числа, докато проследяване на сумата от цифри при даже и странно позиции с помощта на две променливи. За дадена позиция я попълваме с всички цифри от 0 до 9 и в зависимост от това дали текущата позиция е четна или нечетна, увеличаваме четната или нечетната сума. Ние обработваме главните нулеви букви отделно, тъй като те не се броят като цифри.
Следвахме базирано на нула номериране като индекси на масиви. т.е. водещата (най-лявата) цифра се счита за присъстваща на четна позиция, а цифрата до нея се счита за нечетна и т.н.

C++ 
// C++ program to print all n-digit numbers such that // the absolute difference between the sum of digits at // even and odd positions is 1 #include    using namespace std; // Recursive function to generate numbers void findNDigitNumsUtil(int pos int n int num  int evenSum int oddSum  vector<int> &res) {  // If number is formed  if (pos == n) {  // Check absolute difference condition  if (abs(evenSum - oddSum) == 1) {  res.push_back(num);  }  return;  }  // Digits to consider at current position  for (int d = 0; d <= 9; d++) {  // Skip leading 0  if (pos == 0 && d == 0) {  continue;  }  // If position is even (0-based) add to evenSum  if (pos % 2 == 0) {  findNDigitNumsUtil(pos + 1 n num * 10 + d  evenSum + d oddSum res);  }  // If position is odd add to oddSum  else {  findNDigitNumsUtil(pos + 1 n num * 10 + d  evenSum oddSum + d res);  }  } } // Function to prepare and collect valid numbers vector<int> findNDigitNums(int n) {    vector<int> res;  findNDigitNumsUtil(0 n 0 0 0 res);    return res; } // Driver code int main() {  int n = 2;  vector<int> res = findNDigitNums(n);  for (int i = 0; i < res.size(); i++) {  cout << res[i] << ' ';  }  return 0; }
Java 
// Java program to print all n-digit numbers such that // the absolute difference between the sum of digits at // even and odd positions is 1 import java.util.*; class GfG {  // Recursive function to generate numbers  static void findNDigitNumsUtil(int pos int n int num  int evenSum int oddSum  ArrayList<Integer> res) {  // If number is formed  if (pos == n) {  // Check absolute difference condition  if (Math.abs(evenSum - oddSum) == 1) {  res.add(num);  }  return;  }  // Digits to consider at current position  for (int d = 0; d <= 9; d++) {  // Skip leading 0  if (pos == 0 && d == 0) {  continue;  }  // If position is even (0-based) add to evenSum  if (pos % 2 == 0) {  findNDigitNumsUtil(pos + 1 n num * 10 + d  evenSum + d oddSum res);  }  // If position is odd add to oddSum  else {  findNDigitNumsUtil(pos + 1 n num * 10 + d  evenSum oddSum + d res);  }  }  }  // Function to prepare and collect valid numbers  static ArrayList<Integer> findNDigitNums(int n) {  ArrayList<Integer> res = new ArrayList<>();  findNDigitNumsUtil(0 n 0 0 0 res);  return res;  }  // Driver code  public static void main(String[] args) {  int n = 2;  ArrayList<Integer> res = findNDigitNums(n);  // Print all collected valid numbers  for (int i = 0; i < res.size(); i++) {  System.out.print(res.get(i) + ' ');  }  } }
Python 
# Python program to print all n-digit numbers such that # the absolute difference between the sum of digits at # even and odd positions is 1 # Recursive function to generate numbers def findNDigitNumsUtil(pos n num evenSum oddSum res): # If number is formed if pos == n: # Check absolute difference condition if abs(evenSum - oddSum) == 1: res.append(num) return # Digits to consider at current position for d in range(10): # Skip leading 0 if pos == 0 and d == 0: continue # If position is even (0-based) add to evenSum if pos % 2 == 0: findNDigitNumsUtil(pos + 1 n num * 10 + d evenSum + d oddSum res) # If position is odd add to oddSum else: findNDigitNumsUtil(pos + 1 n num * 10 + d evenSum oddSum + d res) # Function to prepare and collect valid numbers def findNDigitNums(n): res = [] findNDigitNumsUtil(0 n 0 0 0 res) return res # Driver code if __name__ == '__main__': n = 2 res = findNDigitNums(n) # Print all collected valid numbers for i in range(len(res)): print(res[i] end=' ')
C# 
// C# program to print all n-digit numbers such that // the absolute difference between the sum of digits at // even and odd positions is 1 using System; using System.Collections.Generic; class GfG {  // Recursive function to generate numbers  static void findNDigitNumsUtil(int pos int n int num  int evenSum int oddSum  List<int> res) {  // If number is formed  if (pos == n) {  // Check absolute difference condition  if (Math.Abs(evenSum - oddSum) == 1) {  res.Add(num);  }  return;  }  // Digits to consider at current position  for (int d = 0; d <= 9; d++) {  // Skip leading 0  if (pos == 0 && d == 0) {  continue;  }  // If position is even (0-based) add to evenSum  if (pos % 2 == 0) {  findNDigitNumsUtil(pos + 1 n num * 10 + d  evenSum + d oddSum res);  }  // If position is odd add to oddSum  else {  findNDigitNumsUtil(pos + 1 n num * 10 + d  evenSum oddSum + d res);  }  }  }  // Function to prepare and collect valid numbers  static List<int> findNDigitNums(int n) {  List<int> res = new List<int>();  findNDigitNumsUtil(0 n 0 0 0 res);  return res;  }  // Driver code  public static void Main(string[] args) {  int n = 2;  List<int> res = findNDigitNums(n);  // Print all collected valid numbers  for (int i = 0; i < res.Count; i++) {  Console.Write(res[i] + ' ');  }  } }
JavaScript 
// JavaScript program to print all n-digit numbers such that // the absolute difference between the sum of digits at // even and odd positions is 1 // Recursive function to generate numbers function findNDigitNumsUtil(pos n num evenSum oddSum res) {  // If number is formed  if (pos === n) {  // Check absolute difference condition  if (Math.abs(evenSum - oddSum) === 1) {  res.push(num);  }  return;  }  // Digits to consider at current position  for (let d = 0; d <= 9; d++) {  // Skip leading 0  if (pos === 0 && d === 0) {  continue;  }  // If position is even (0-based) add to evenSum  if (pos % 2 === 0) {  findNDigitNumsUtil(pos + 1 n num * 10 + d  evenSum + d oddSum res);  }  // If position is odd add to oddSum  else {  findNDigitNumsUtil(pos + 1 n num * 10 + d  evenSum oddSum + d res);  }  } } // Function to prepare and collect valid numbers function findNDigitNums(n) {  let res = [];  findNDigitNumsUtil(0 n 0 0 0 res);  return res; } // Driver code let n = 2; let res = findNDigitNums(n); // Print all collected valid numbers for (let i = 0; i < res.length; i++) {  process.stdout.write(res[i] + ' '); }

Изход 
10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98

Времева сложност: O(9 × 10^(n-1)), тъй като всяка цифра има до 10 избора (с изключение на първата, която има 9).
Космическа сложност: O(n + k), където n е дълбочината на рекурсия и k е броят на валидните резултати.