Dados dos números enteros N y K , la tarea es encontrar el recuento total del número de N dígitos tal que la suma de cada K dígitos consecutivos del número sea igual.
Ejemplos:
Entrada: N = 2, K = 1
Salida: 9
Explicación:
Los números son 11, 22, 33, 44, 55, 66, 77, 88, 99 con suma de cada 1 dígitos consecutivos igual a 1, 2, 3, 4 , 5, 6, 7, 8, 9 respectivamente.Entrada: N = 3, K = 2
Salida: 90
Enfoque ingenuo: iterar para todos los números posibles de N dígitos y calcular la suma de cada K dígitos consecutivos del número. Si todas las sumas son iguales, incluya este es el conteo; de lo contrario, verifique el siguiente número.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for
// the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to count the number of
// N-digit numbers such that sum of
// every k consecutive digits are equal
int countDigitSum(int N, int K)
{
// Range of numbers
int l = (int)pow(10, N - 1),
r = (int)pow(10, N) - 1;
int count = 0;
for(int i = l; i <= r; i++)
{
int num = i;
// Extract digits of the number
int digits[N];
for(int j = N - 1; j >= 0; j--)
{
digits[j] = num % 10;
num /= 10;
}
int sum = 0, flag = 0;
// Store the sum of first K digits
for(int j = 0; j < K; j++)
sum += digits[j];
// Check for every
// k-consecutive digits
for(int j = 1; j < N - K + 1; j++)
{
int curr_sum = 0;
for(int m = j; m < j + K; m++)
curr_sum += digits[m];
// If sum is not equal
// then break the loop
if (sum != curr_sum)
{
flag = 1;
break;
}
}
// Increment the count if it
// satisfy the given condition
if (flag == 0)
{
count++;
}
}
return count;
}
// Driver Code
int main()
{
// Given N and K
int N = 2, K = 1;
// Function call
cout << countDigitSum(N, K);
return 0;
}
// This code is contributed by target_2.
C
// C program for the above approach
#include <math.h>
#include <stdio.h>
// Function to count the number of
// N-digit numbers such that sum of
// every k consecutive digits are equal
int countDigitSum(int N, int K)
{
// Range of numbers
int l = (int)pow(10, N - 1),
r = (int)pow(10, N) - 1;
int count = 0;
for(int i = l; i <= r; i++)
{
int num = i;
// Extract digits of the number
int digits[N];
for(int j = N - 1; j >= 0; j--)
{
digits[j] = num % 10;
num /= 10;
}
int sum = 0, flag = 0;
// Store the sum of first K digits
for(int j = 0; j < K; j++)
sum += digits[j];
// Check for every
// k-consecutive digits
for(int j = 1; j < N - K + 1; j++)
{
int curr_sum = 0;
for(int m = j; m < j + K; m++)
curr_sum += digits[m];
// If sum is not equal
// then break the loop
if (sum != curr_sum)
{
flag = 1;
break;
}
}
// Increment the count if it
// satisfy the given condition
if (flag == 0)
{
count++;
}
}
return count;
}
// Driver code
int main()
{
// Given N and K
int N = 2, K = 1;
// Function call
printf("%d", countDigitSum(N, K));
return 0;
}
// This code is contributed by piyush3010
Java
// Java program for the above approach
class GFG {
// Function to count the number of
// N-digit numbers such that sum of
// every k consecutive digits are equal
static int countDigitSum(int N, int K)
{
// Range of numbers
int l = (int)Math.pow(10, N - 1),
r = (int)Math.pow(10, N) - 1;
int count = 0;
for (int i = l; i <= r; i++) {
int num = i;
// Extract digits of
// the number
int digits[] = new int[N];
for (int j = N - 1;
j >= 0; j--) {
digits[j] = num % 10;
num /= 10;
}
int sum = 0, flag = 0;
// Store the sum of
// first K digits
for (int j = 0; j < K; j++)
sum += digits[j];
// Check for every
// k-consecutive digits
for (int j = 1;
j < N - K + 1; j++) {
int curr_sum = 0;
for (int m = j;
m < j + K; m++) {
curr_sum += digits[m];
}
// If sum is not equal
// then break the loop
if (sum != curr_sum) {
flag = 1;
break;
}
}
// Increment the count if it
// satisfy the given condition
if (flag == 0) {
count++;
}
}
return count;
}
// Driver Code
public static void
main(String[] args)
{
// Given N and K
int N = 2, K = 1;
// Function call
System.out.print(countDigitSum(N, K));
}
}
Python3
# Python3 program for the above approach # Function to count the number of # N-digit numbers such that sum of # every k consecutive digits are equal def countDigitSum(N, K): # Range of numbers l = pow(10, N - 1) r = pow(10, N) - 1 count = 0 for i in range(l, r + 1): num = i # Extract digits of the number digits = [0] * N for j in range(N - 1, -1, -1): digits[j] = num % 10 num //= 10 sum = 0 flag = 0 # Store the sum of first K digits for j in range(0, K): sum += digits[j] # Check for every # k-consecutive digits for j in range(1, N - K + 1): curr_sum = 0 for m in range(j, j + K): curr_sum += digits[m] # If sum is not equal # then break the loop if (sum != curr_sum): flag = 1 break # Increment the count if it # satisfy the given condition if (flag == 0): count += 1 return count # Driver code # Given N and K N = 2 K = 1 # Function call print(countDigitSum(N, K)) # This code is contributed by sanjoy_62
C#
// C# program for the above approach
using System;
class GFG{
// Function to count the number of
// N-digit numbers such that sum of
// every k consecutive digits are equal
static int countDigitSum(int N, int K)
{
// Range of numbers
int l = (int)Math.Pow(10, N - 1),
r = (int)Math.Pow(10, N) - 1;
int count = 0;
for(int i = l; i <= r; i++)
{
int num = i;
// Extract digits of
// the number
int[] digits = new int[N];
for(int j = N - 1; j >= 0; j--)
{
digits[j] = num % 10;
num /= 10;
}
int sum = 0, flag = 0;
// Store the sum of
// first K digits
for(int j = 0; j < K; j++)
sum += digits[j];
// Check for every
// k-consecutive digits
for(int j = 1; j < N - K + 1; j++)
{
int curr_sum = 0;
for(int m = j; m < j + K; m++)
{
curr_sum += digits[m];
}
// If sum is not equal
// then break the loop
if (sum != curr_sum)
{
flag = 1;
break;
}
}
// Increment the count if it
// satisfy the given condition
if (flag == 0)
{
count++;
}
}
return count;
}
// Driver Code
public static void Main()
{
// Given N and K
int N = 2, K = 1;
// Function call
Console.Write(countDigitSum(N, K));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for the above approach
// Function to count the number of
// N-digit numbers such that sum of
// every k consecutive digits are equal
function countDigitSum(N, K)
{
// Range of numbers
let l = parseInt(Math.pow(10, N - 1)),
r = parseInt(Math.pow(10, N) - 1);
let count = 0;
for(let i = l; i <= r; i++)
{
let num = i;
// Extract digits of the number
let digits = new Array(N);
for(let j = N - 1; j >= 0; j--)
{
digits[j] = num % 10;
num = parseInt(num/10);
}
let sum = 0, flag = 0;
// Store the sum of first K digits
for(let j = 0; j < K; j++)
sum += digits[j];
// Check for every
// k-consecutive digits
for(let j = 1; j < N - K + 1; j++)
{
let curr_sum = 0;
for(let m = j; m < j + K; m++)
curr_sum += digits[m];
// If sum is not equal
// then break the loop
if (sum != curr_sum)
{
flag = 1;
break;
}
}
// Increment the count if it
// satisfy the given condition
if (flag == 0)
{
count++;
}
}
return count;
}
// Driver code
// Given N and K
let N = 2, K = 1;
// Function call
document.write(countDigitSum(N, K));
// This code is contributed by souravmahato348.
</script>
Producción:
9
Complejidad temporal: O(10 N * N * K)
Espacio auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque ingenuo anterior, la idea es utilizar la técnica de la ventana deslizante para verificar si la suma de K dígitos consecutivos del número es igual o no. A continuación se muestran los pasos:
- Obtenga el rango de números, es decir, 10 N -1 a 10 N.
- Para cada número en el rango anterior, considere una ventana de longitud K y encuentre la suma de cada dígito . Almacene esta suma como S .
- Encuentre la suma de los siguientes K dígitos usando la ventana deslizante incluyendo los siguientes K dígitos en la suma y elimine los K dígitos anteriores de la suma.
- Si la suma obtenida es igual a la suma S anterior , verifique los siguientes K dígitos.
- De lo contrario, repita el paso anterior para los siguientes números.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of
// N-digit numbers such that sum of
// every k consecutive digits are equal
int countDigitSum(int N, int K)
{
// Range of numbers
int l = (int)pow(10, N - 1),
r = (int)pow(10, N) - 1;
int count = 0;
for(int i = l; i <= r; i++)
{
int num = i;
// Extract digits of the number
int digits[N];
for (int j = N - 1; j >= 0; j--)
{
digits[j] = num % 10;
num /= 10;
}
int sum = 0, flag = 0;
// Store the sum of first K digits
for(int j = 0; j < K; j++)
sum += digits[j];
// Check for every
// k-consecutive digits
// using sliding window
for(int j = K; j < N; j++)
{
if(sum - digits[j - K] +
digits[j] != sum)
{
flag = 1;
break;
}
}
if (flag == 0)
count++;
}
return count;
}
// Driver Code
int main()
{
// Given integer N and K
int N = 2, K = 1;
cout<< countDigitSum(N, K)<<endl;
return 0;
}
// This code is contributed by itsok.
C
// C program for the above approach
#include <stdio.h>
#include <math.h>
// Function to count the number of
// N-digit numbers such that sum of
// every k consecutive digits are equal
int countDigitSum(int N, int K)
{
// Range of numbers
int l = (int)pow(10, N - 1),
r = (int)pow(10, N) - 1;
int count = 0;
for(int i = l; i <= r; i++)
{
int num = i;
// Extract digits of the number
int digits[N];
for (int j = N - 1; j >= 0; j--)
{
digits[j] = num % 10;
num /= 10;
}
int sum = 0, flag = 0;
// Store the sum of first K digits
for(int j = 0; j < K; j++)
sum += digits[j];
// Check for every
// k-consecutive digits
// using sliding window
for(int j = K; j < N; j++)
{
if(sum - digits[j - K] +
digits[j] != sum)
{
flag = 1;
break;
}
}
if (flag == 0)
count++;
}
return count;
}
// Driver Code
int main()
{
// Given integer N and K
int N = 2, K = 1;
printf("%d", countDigitSum(N, K));
return 0;
}
// This code is contributed by piyush3010
Java
// Java program for the above approach
class GFG {
// Function to count the number of
// N-digit numbers such that sum of
// every k consecutive digits are equal
static int countDigitSum(int N, int K)
{
// Range of numbers
int l = (int)Math.pow(10, N - 1),
r = (int)Math.pow(10, N) - 1;
int count = 0;
for (int i = l; i <= r; i++) {
int num = i;
// Extract digits of the number
int digits[] = new int[N];
for (int j = N - 1; j >= 0; j--) {
digits[j] = num % 10;
num /= 10;
}
int sum = 0, flag = 0;
// Store the sum of
// first K digits
for (int j = 0; j < K; j++)
sum += digits[j];
// Check for every
// k-consecutive digits
// using sliding window
for (int j = K; j < N; j++) {
if (sum - digits[j - K]
+ digits[j]
!= sum) {
flag = 1;
break;
}
}
if (flag == 0) {
count++;
}
}
return count;
}
// Driver Code
public static void main(String[] args)
{
// Given integer N and K
int N = 2, K = 1;
System.out.print(countDigitSum(N, K));
}
}
/* This code is contributed by piyush3010 */
Python3
# Python3 program for the # above approach # Function to count the # number of N-digit numbers # such that sum of every k # consecutive digits are equal def countDigitSum(N, K): # Range of numbers l = pow(10, N - 1); r = pow(10, N) - 1; count = 0; for i in range(1, r + 1): num = i; # Extract digits of # the number digits = [0] * (N); for j in range(N - 1, 0, -1): digits[j] = num % 10; num //= 10; sum = 0; flag = 0; # Store the sum of # first K digits for j in range(0, K): sum += digits[j]; # Check for every # k-consecutive digits # using sliding window for j in range(K, N): if (sum - digits[j - K] + digits[j] != sum): flag = 1; break; if (flag == 0): count += 1; return count; # Driver Code if __name__ == '__main__': # Given integer N and K N = 2; K = 1; print(countDigitSum(N, K)); # This code is contributed by shikhasingrajput
C#
// C# program for the above approach
using System;
class GFG{
// Function to count the number of
// N-digit numbers such that sum of
// every k consecutive digits are equal
static int countDigitSum(int N, int K)
{
// Range of numbers
int l = (int)Math.Pow(10, N - 1),
r = (int)Math.Pow(10, N) - 1;
int count = 0;
for(int i = l; i <= r; i++)
{
int num = i;
// Extract digits of the number
int[] digits = new int[N];
for(int j = N - 1; j >= 0; j--)
{
digits[j] = num % 10;
num /= 10;
}
int sum = 0, flag = 0;
// Store the sum of
// first K digits
for(int j = 0; j < K; j++)
sum += digits[j];
// Check for every
// k-consecutive digits
// using sliding window
for(int j = K; j < N; j++)
{
if (sum - digits[j - K] +
digits[j] != sum)
{
flag = 1;
break;
}
}
if (flag == 0)
{
count++;
}
}
return count;
}
// Driver Code
public static void Main()
{
// Given N and K
int N = 2, K = 1;
// Function call
Console.Write(countDigitSum(N, K));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for the above approach
// Function to count the number of
// N-digit numbers such that sum of
// every k consecutive digits are equal
function countDigitSum(N , K)
{
// Range of numbers
var l = parseInt( Math.pow(10, N - 1)),
var r = parseInt( Math.pow(10, N) - 1);
var count = 0;
for (i = l; i <= r; i++) {
var num = i;
// Extract digits of the number
var digits = Array(N).fill(0);
for (j = N - 1; j >= 0; j--) {
digits[j] = num % 10;
num = parseInt(num/10);
}
var sum = 0, flag = 0;
// Store the sum of
// first K digits
for (j = 0; j < K; j++)
sum += digits[j];
// Check for every
// k-consecutive digits
// using sliding window
for (j = K; j < N; j++) {
if (sum - digits[j - K] + digits[j] != sum) {
flag = 1;
break;
}
}
if (flag == 0) {
count++;
}
}
return count;
}
// Driver Code
// Given integer N and K
var N = 2, K = 1;
document.write(countDigitSum(N, K));
// This code contributed by umadevi9616
</script>
Producción:
9
Complejidad temporal: O(10 N *N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por jrishabh99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA