Dada la cantidad de dígitos n, imprima todos los números de n dígitos cuya diferencia absoluta entre la suma de los dígitos en posiciones pares e impares sea 1. La solución no debe considerar los ceros iniciales como dígitos.
Ejemplos:
Input: n = 2 Output: 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98 Input: n = 3 Output: 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
La idea es generar todos los números de n dígitos usando la recursividad y mantener la suma de los dígitos pares e impares hasta ahora en dos variables separadas. Para una posición determinada, la llenamos con todos los dígitos del 0 al 9 y, según si la posición actual es par o impar, incrementamos la suma par o impar. Manejamos el caso de los 0 iniciales por separado, ya que no se cuentan como dígitos.
Hemos seguido la numeración basada en cero como índices de array. es decir, se considera que el dígito inicial (más a la izquierda) está presente en una posición par y el dígito siguiente se considera en una posición impar, y así sucesivamente.
A continuación se muestra la implementación de la idea anterior:
C++
// A C++ recursive program to print all N-digit numbers with
// absolute difference between sum of even and odd digits is 1
#include <bits/stdc++.h>
using namespace std;
// Recursive function to print all N-digit numbers with absolute
// difference between sum of even and odd digits is 1.
// This function considers leading zero as a digit
// n --> value of input
// out --> output array
// index --> index of next digit to be filled in output array
// evenSum, oddSum --> sum of even and odd digits so far
void findNDigitNumsUtil(int n, char* out, int index, int evenSum,
int oddSum)
{
// Base case
if (index > n)
return;
// If number becomes n-digit
if (index == n)
{
// if absolute difference between sum of even and
// odd digits is 1, print the number
if (abs(evenSum - oddSum) == 1)
{
out[index] = ' ';
cout << out;
}
return;
}
// If current index is odd, then add it to odd sum and recurse
if (index & 1)
{
for (int i = 0; i <= 9; i++)
{
out[index] = i + '0';
findNDigitNumsUtil(n, out, index + 1, evenSum, oddSum + i);
}
}
else // else add to even sum and recurse
{
for (int i = 0; i <= 9; i++)
{
out[index] = i + '0';
findNDigitNumsUtil(n, out, index + 1, evenSum + i, oddSum);
}
}
}
// This is mainly a wrapper over findNDigitNumsUtil.
// It explicitly handles leading digit and calls
// findNDigitNumsUtil() for remaining indexes.
int findNDigitNums(int n)
{
// output array to store n-digit numbers
char out[n + 1];
// Initialize number index considered so far
int index = 0;
// Initialize even and odd sums
int evenSum = 0, oddSum = 0;
// Explicitly handle first digit and call recursive function
// findNDigitNumsUtil for remaining indexes. Note that the
// first digit is considered to be present in even position.
for (int i = 1; i <= 9; i++)
{
out[index] = i + '0';
findNDigitNumsUtil(n, out, index + 1, evenSum + i, oddSum);
}
}
// Driver program
int main()
{
int n = 3;
findNDigitNums(n);
return 0;
}
Java
// Java program to print all n-digit numbers
// with absolute difference between sum
// of even and odd digits is 1
import java.io.*;
import java.util.*;
class GFG
{
// Recursive function to print all N-digit numbers
// with absolute difference between sum of even
// and odd digits is 1. This function considers
// leading zero as a digit
// n --> value of input
// out --> output array
// index --> index of next digit to be filled in output array
// evenSum, oddSum --> sum of even and odd digits so far
static void findNDigitNumsUtil(int n, char out[], int index,
int evenSum, int oddSum)
{
// Base case
if (index > n)
return;
// If number becomes n-digit
if (index == n)
{
// if absolute difference between sum of even and
// odd digits is 1, print the number
if (Math.abs(evenSum - oddSum) == 1)
{
out[index] = ' ';
System.out.print(out);
}
return;
}
// If current index is odd, then add it to odd sum and recurse
if (index % 2 != 0)
{
for (int i = 0; i <= 9; i++)
{
out[index] = (char)(i + '0');
findNDigitNumsUtil(n, out, index + 1, evenSum, oddSum + i);
}
}
else // else add to even sum and recurse
{
for (int i = 0; i <= 9; i++)
{
out[index] = (char)(i + '0');
findNDigitNumsUtil(n, out, index + 1, evenSum + i, oddSum);
}
}
}
// This is mainly a wrapper over findNDigitNumsUtil.
// It explicitly handles leading digit and calls
// findNDigitNumsUtil() for remaining indexes
static void findNDigitNums(int n)
{
// output array to store n-digit numbers
char[] out = new char[n + 1];
// Initialize number index considered so far
int index = 0;
// Initialize even and odd sums
int evenSum = 0, oddSum = 0;
// Explicitly handle first digit and call recursive function
// findNDigitNumsUtil for remaining indexes. Note that the
// first digit is considered to be present in even position
for (int i = 1; i <= 9; i++)
{
out[index] = (char)(i + '0');
findNDigitNumsUtil(n, out, index + 1, evenSum + i, oddSum);
}
}
// Driver program
public static void main (String[] args)
{
int n = 3;
findNDigitNums(n);
}
}
// This code is contributed by Pramod Kumar
Python 3
# Python 3 recursive program to print all N-digit
# numbers with absolute difference between sum of
# even and odd digits is 1
# Recursive function to print all N-digit numbers
# with absolute difference between sum of even and
# odd digits is 1. This function considers leading
# zero as a digit
# n --> value of input
# out --> output array
# index --> index of next digit to be filled
# in output array
# evenSum, oddSum --> sum of even and odd
# digits so far
def findNDigitNumsUtil(n, out, index,
evenSum, oddSum):
# Base case
if (index > n):
return
# If number becomes n-digit
if (index == n):
# if absolute difference between sum of even
# and odd digits is 1, print the number
if (abs(evenSum - oddSum) == 1):
out[index] = ''
out = ''.join(out)
print(out, end = " ")
return
# If current index is odd, then add it
# to odd sum and recurse
if (index & 1):
for i in range(10):
out[index] = chr(i + ord('0'))
findNDigitNumsUtil(n, out, index + 1,
evenSum, oddSum + i)
else: # else add to even sum and recurse
for i in range(10):
out[index] = chr(i + ord('0'))
findNDigitNumsUtil(n, out, index + 1,
evenSum + i, oddSum)
# This is mainly a wrapper over findNDigitNumsUtil.
# It explicitly handles leading digit and calls
# findNDigitNumsUtil() for remaining indexes.
def findNDigitNums(n):
# output array to store n-digit numbers
out = [0] * (n + 1)
# Initialize number index considered
# so far
index = 0
# Initialize even and odd sums
evenSum = 0
oddSum = 0
# Explicitly handle first digit and call
# recursive function findNDigitNumsUtil
# for remaining indexes. Note that the
# first digit is considered to be present
# in even position.
for i in range(1, 10):
out[index] = chr(i + ord('0'))
findNDigitNumsUtil(n, out, index + 1,
evenSum + i, oddSum)
# Driver Code
if __name__ == "__main__":
n = 3
findNDigitNums(n)
# This code is contributed by ita_c
C#
// C# program to print all n-digit numbers
// with absolute difference between sum
// of even and odd digits is 1
using System;
class GFG {
// Recursive function to print all N-digit
// numbers with absolute difference between
// sum of even and odd digits is 1. This
// function considers leading zero as a
// digit
// n --> value of input
// out --> output array
// index --> index of next digit to be
// filled in output array
// evenSum, oddSum --> sum of even and
// odd digits so far
static void findNDigitNumsUtil(int n, char []ou,
int index, int evenSum, int oddSum)
{
// Base case
if (index > n)
return;
// If number becomes n-digit
if (index == n)
{
// if absolute difference between sum
// of even and odd digits is 1, print
// the number
if (Math.Abs(evenSum - oddSum) == 1)
{
ou[index] = '\0';
Console.Write(ou);
Console.Write(" ");
}
return;
}
// If current index is odd, then add it
// to odd sum and recurse
if (index % 2 != 0)
{
for (int i = 0; i <= 9; i++)
{
ou[index] = (char)(i + '0');
findNDigitNumsUtil(n, ou, index + 1,
evenSum, oddSum + i);
}
}
else // else add to even sum and recurse
{
for (int i = 0; i <= 9; i++)
{
ou[index] = (char)(i + '0');
findNDigitNumsUtil(n, ou, index + 1,
evenSum + i, oddSum);
}
}
}
// This is mainly a wrapper over findNDigitNumsUtil.
// It explicitly handles leading digit and calls
// findNDigitNumsUtil() for remaining indexes
static void findNDigitNums(int n)
{
// output array to store n-digit numbers
char []ou = new char[n + 1];
// Initialize number index considered so far
int index = 0;
// Initialize even and odd sums
int evenSum = 0, oddSum = 0;
// Explicitly handle first digit and call
// recursive function findNDigitNumsUtil for
// remaining indexes. Note that the first
// digit is considered to be present in even
// position
for (int i = 1; i <= 9; i++)
{
ou[index] = (char)(i + '0');
findNDigitNumsUtil(n, ou, index + 1,
evenSum + i, oddSum);
}
}
// Driver program
public static void Main ()
{
int n = 3;
findNDigitNums(n);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// A PHP recursive program to print
// all N-digit numbers with absolute
// difference between sum of even
// and odd digits is 1
// Recursive function to print all
// N-digit numbers with absolute
// difference between sum of even
// and odd digits is 1. This function
// considers leading zero as a digit
// n --> value of input
// out --> output array
// index --> index of next digit
// to be filled in output array
// evenSum, oddSum --> sum of even
// and odd digits so far
function findNDigitNumsUtil($n,$out, $index, $evenSum,$oddSum)
{
// Base case
if ($index > $n)
return;
// If number becomes n-digit
if ($index == $n)
{
// if absolute difference between sum of even and
// odd digits is 1, print the number
if (abs($evenSum - $oddSum) == 1)
{
echo implode("",$out)." ";
}
return;
}
// If current index is odd, then
// add it to odd sum and recurse
if ($index & 1)
{
for ($i = 0; $i <= 9; $i++)
{
$out[$index] = $i + '0';
findNDigitNumsUtil($n, $out, $index + 1,
$evenSum, $oddSum + $i);
}
}
else // else add to even sum and recurse
{
for ($i = 0; $i <= 9; $i++)
{
$out[$index] = $i + '0';
findNDigitNumsUtil($n, $out, $index + 1,
$evenSum + $i, $oddSum);
}
}
}
// This is mainly a wrapper over findNDigitNumsUtil.
// It explicitly handles leading digit and calls
// findNDigitNumsUtil() for remaining indexes.
function findNDigitNums($n)
{
// output array to store n-digit numbers
$out=array_fill(0,$n + 1,"");
// Initialize number index considered so far
$index = 0;
// Initialize even and odd sums
$evenSum = 0;
$oddSum = 0;
// Explicitly handle first digit and
// call recursive function findNDigitNumsUtil
// for remaining indexes. Note that the
// first digit is considered to be present in even position.
for ($i = 1; $i <= 9; $i++)
{
$out[$index] = $i + '0';
findNDigitNumsUtil($n, $out, $index + 1,
$evenSum + $i, $oddSum);
}
}
// Driver program
$n = 3;
findNDigitNums($n);
// This code is contributed by chandan_jnu
?>
Javascript
<script>
// Javascript program to print all n-digit numbers
// with absolute difference between sum
// of even and odd digits is 1
// Recursive function to print all N-digit numbers
// with absolute difference between sum of even
// and odd digits is 1. This function considers
// leading zero as a digit
// n --> value of input
// out --> output array
// index --> index of next digit to be filled in output array
// evenSum, oddSum --> sum of even and odd digits so far
function findNDigitNumsUtil(n, out, index, evenSum, oddSum)
{
// Base case
if (index > n)
return;
// If number becomes n-digit
if (index == n)
{
// if absolute difference between sum of even and
// odd digits is 1, print the number
if (Math.abs(evenSum - oddSum) == 1)
{
out[index] = '';
for(let i = 0; i < out.length; i++)
{
document.write(out[i]);
}
document.write(" ");
}
return;
}
// If current index is odd, then add it to odd sum and recurse
if (index % 2 != 0)
{
for (let i = 0; i <= 9; i++)
{
out[index] = String.fromCharCode(i + '0'.charCodeAt(0));
findNDigitNumsUtil(n, out, index + 1, evenSum, oddSum + i);
}
}
else // else add to even sum and recurse
{
for (let i = 0; i <= 9; i++)
{
out[index] = String.fromCharCode(i + '0'.charCodeAt(0));
findNDigitNumsUtil(n, out, index + 1, evenSum + i, oddSum);
}
}
}
// This is mainly a wrapper over findNDigitNumsUtil.
// It explicitly handles leading digit and calls
// findNDigitNumsUtil() for remaining indexes
function findNDigitNums(n)
{
let out = new Array(n+1);
for(let i=0;i<n+1;i++)
{
out[i]=0;
}
// Initialize number index considered so far
let index = 0;
// Initialize even and odd sums
let evenSum = 0, oddSum = 0;
// Explicitly handle first digit and call recursive function
// findNDigitNumsUtil for remaining indexes. Note that the
// first digit is considered to be present in even position
for (let i = 1; i <= 9; i++)
{
out[index] = String.fromCharCode(i + '0'.charCodeAt(0));
findNDigitNumsUtil(n, out, index + 1, evenSum + i, oddSum);
}
}
// Driver program
let n = 3;
findNDigitNums(n);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
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
Podemos evitar el uso de dos variables evenSum y oddSum. En su lugar, podemos mantener la diferencia de una sola variable que almacena la diferencia entre la suma de los dígitos pares e impares. La implementación se puede ver aquí .
Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA