Given N, the number of digits of an integer which is greater than or equal to 2 and a weight W. The task is to find the count of integers that have N digits and weight W.
Note: Weight is defined as the difference between the consecutive digits of an integer.
Examples:
Input : N = 2, W = 3 Output : 6 Input : N = 2, W = 4 Output : 5
In the above example, the total possible 2 digit integers with a weight equal to 3 will be 6. Like the number 14 has weight 3 (4-1) and 25, 36, 47, 58, 69 has weight 3. If we see it carefully we’ll find the logic that if we increment the weight as 5 of a 2-digit number, then the total possible such numbers will be 5. With weight 6 of a 2-digit number, the total possible numbers will be 4 and then 3 and so on. Also, if we increase the number of digits. Say, n equal to 3 with weight 3, then the total possible numbers will be 60 and 600 for n equal to 4 with weight 3 and so on.
Number of digits | Weight —> Total possible such numbers
| 2|2 —> 7 | 2|3 —> 6 | 2|4 —> 5 | 2|5 —> 4 | 2|6 —> 3 | 2|7 —> 2 | 2|8 —> 1 |
| 3|2 —> 70 | 3|3 —> 60 | 3|4 —> 50 | 3|5 —> 40 | 3|6 —> 30 | 3|7 —> 20 | 3|8 —> 10 |
| 4|2 —>700 | 4|3 —>600 | 4|4 —>500 | 4|5 —>400 | 4|6 —>300 | 4|7 —>200 | 4|8 —>100 |
As you can see in the above table that with an increase in the number of digits, the number of numbers with weight ‘w’ is following a pattern, where it is changing in the multiple of 10^(n-2), where ‘n’ is the number of digits.
Below is the step by step algorithm to solve this problem:
- Check if the given Weight(W) is Positive or Negative.
- Subtract Weight(W) from 9 if positive.
- Add Weight to 10 if it is negative and then update the new weight.
- For n digit integer, multiply 10^(n-2) with this updated weight.
- This will give us the number of integers satisfying this weight.
Below is the implementation of above approach:
C++
// CPP program to find total possible numbers// with n digits and weight w#include <iostream>#include<cmath>using namespace std;// Function to find total possible numbers// with n digits and weight wint findNumbers(int n, int w){ int x = 0, sum = 0; // When Weight of an integer is Positive if (w >= 0 && w <= 8) { // Subtract the weight from 9 x = 9 - w; } // When weight of an integer is negative else if (w >= -9 && w <= -1) { // add the weight to 10 to make it positive x = 10 + w; } sum = pow(10, n - 2); sum = (x * sum); return sum;}// Driver codeint main(){ int n, w; // number of digits in an // integer and w as weight n = 3, w = 4; // print the total possible numbers // with n digits and weight w cout << findNumbers(n, w);; return 0;} |
Java
// Java program to find total // possible numbers with n// digits and weight wclass GFG{ // Function to find total // possible numbers with n// digits and weight wstatic int findNumbers(int n, int w){ int x = 0, sum = 0; // When Weight of an // integer is Positive if (w >= 0 && w <= 8) { // Subtract the weight from 9 x = 9 - w; } // When weight of an // integer is negative else if (w >= -9 && w <= -1) { // add the weight to 10 // to make it positive x = 10 + w; } sum = (int)Math.pow(10, n - 2); sum = (x * sum); return sum;}// Driver codepublic static void main(String args[]){ int n, w; // number of digits in an // integer and w as weight n = 3; w = 4; // print the total possible numbers // with n digits and weight w System.out.println(findNumbers(n, w));} }// This code is contributed // by ankita_saini |
Python3
# Python3 program to find total possible # numbers with n digits and weight w# Function to find total possible # numbers with n digits and weight wdef findNumbers(n, w): x = 0; sum = 0; # When Weight of an integer # is Positive if (w >= 0 and w <= 8): # Subtract the weight from 9 x = 9 - w; # When weight of an integer # is negative elif (w >= -9 and w <= -1): # add the weight to 10 to # make it positive x = 10 + w; sum = pow(10, n - 2); sum = (x * sum); return sum;# Driver code# number of digits in an# integer and w as weightn = 3; w = 4;# print the total possible numbers# with n digits and weight wprint(findNumbers(n, w));# This code is contributed # by mits |
C#
// C# program to find total possible // numbers with n digits and weight wusing System;class GFG{ // Function to find total possible // numbers with n digits and weight w static int findNumbers(int n, int w) { int x = 0, sum = 0; // When Weight of an integer // is Positive if (w >= 0 && w <= 8) { // Subtract the weight from 9 x = 9 - w; } // When weight of an // integer is negative else if (w >= -9 && w <= -1) { // add the weight to 10 // to make it positive x = 10 + w; } sum = (int)Math.Pow(10, n - 2); sum = (x * sum); return sum; } // Driver code static public void Main (){ int n, w; // number of digits in an // integer and w as weight n = 3; w = 4; // print the total possible numbers // with n digits and weight w Console.WriteLine(findNumbers(n, w)); } } // This code is contributed by jit_t |
PHP
<?php// PHP program to find total possible // numbers with n digits and weight w// Function to find total possible // numbers with n digits and weight wfunction findNumbers($n, $w){ $x = 0; $sum = 0; // When Weight of an integer // is Positive if ($w >= 0 && $w <= 8) { // Subtract the weight from 9 $x = 9 - $w; } // When weight of an integer // is negative else if ($w >= -9 && $w <= -1) { // add the weight to 10 to // make it positive $x = 10 + $w; } $sum = pow(10, $n - 2); $sum = ($x * $sum); return $sum;}// Driver code// number of digits in an// integer and w as weight$n = 3; $w = 4;// print the total possible numbers// with n digits and weight wecho findNumbers($n, $w);// This code is contributed // by Akanksha Rai |
Javascript
<script> // Javascript program to find total possible // numbers with n digits and weight w // Function to find total possible // numbers with n digits and weight w function findNumbers(n, w) { let x = 0, sum = 0; // When Weight of an integer // is Positive if (w >= 0 && w <= 8) { // Subtract the weight from 9 x = 9 - w; } // When weight of an // integer is negative else if (w >= -9 && w <= -1) { // add the weight to 10 // to make it positive x = 10 + w; } sum = Math.pow(10, n - 2); sum = (x * sum); return sum; } let n, w; // number of digits in an // integer and w as weight n = 3; w = 4; // print the total possible numbers // with n digits and weight w document.write(findNumbers(n, w)); </script> |
Output:
50
Time Complexity: O(log(n))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
