Given two integers N and K, the task is to find the count of all possible N-digit numbers having sum of every K consecutive digits of the number are equal.
Examples:
Input: N = 2, K=1
Output: 9
Explanation:
All two digit numbers satisfying the required conditions are {11, 22, 33, 44, 55, 66, 77, 88, 99}
Input: N = 3, K = 2
Output: 90
Naive and Sliding Window Approach: Refer to Count of N digit Numbers whose sum of every K consecutive digits is equal for the simplest approach and Sliding Window technique based approach.
Logarithmic Approach:
For the sum of K-consecutive elements to be always equal, the entire number is governed by its first K digits.
- The ith digit will be equal to the (i-k)th digit for the number to satisfy the condition such that the sum of every K consecutive digit is the same.
Illustration:
N = 5 and K = 2
If the first two digits are 1 and 2, then the number has to be 12121 so that sum of every 2 consecutive digits is 3.
Observe that the first 2 digits i.e. the first K digits repeats itself.
Therefore, to solve the problem, the task is now to find out the total count of K-digit numbers which is equal to 10K – 10(K-1). Therefore, print the calculated value as the answer.
Below is the implementation of the above approach:
C++
// C++ Program to implement// 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 equalvoid count(int n, int k){ long count = (long)(pow(10, k) - pow(10, k - 1)); // Print the answer cout << (count);}// Driver Codeint main(){ int n = 2, k = 1; count(n, k);}// This code is contributed by Ritik Bansal |
Java
// Java Program to implement// the above approachclass GFG { // Function to count the number of // N-digit numbers such that sum of // every K consecutive digits are equal public static void count(int n, int k) { long count = (long)(Math.pow(10, k) - Math.pow(10, k - 1)); // Print the answer System.out.print(count); } // Driver Code public static void main(String[] args) { int n = 2, k = 1; count(n, k); }} |
Python3
# Python3 program to implement# the above approach# Function to count the number of# N-digit numbers such that sum of# every K consecutive digits are equaldef count(n, k): count = (pow(10, k) - pow(10, k - 1)); # Print the answer print(count); # Driver Codeif __name__ == '__main__': n = 2; k = 1; count(n, k); # This code is contributed by 29AjayKumar |
C#
// C# Program to implement// the above approachusing System;class GFG{ // Function to count the number of // N-digit numbers such that sum of // every K consecutive digits are equal public static void count(int n, int k) { long count = (long)(Math.Pow(10, k) - Math.Pow(10, k - 1)); // Print the answer Console.Write(count); } // Driver Code public static void Main(String[] args) { int n = 2, k = 1; count(n, k); }}// This code is contributed by Rohit_ranjan |
Javascript
<script>// Javascript Program to implement// the above approach// Function to count the number of// N-digit numbers such that sum of// every K consecutive digits are equalfunction count(n, k){ let count = Math.pow(10, k) - Math.pow(10, k - 1); // Print the answer document.write(count);}// Driver Codelet n = 2, k = 1;count(n, k);// This code is contributed by souravmahato348.</script> |
9
Time Complexity: O(log K)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
