A number of N digits composed of M numbers that is divisible by 5 written in C++

We are given a number N and an array of M digits. Our job is to find n numbers A number divisible by 5 consisting of the given M digits.

Let's look at some examples to understand the input and output of the problem.

In -

N = 2
M = 3
arr = {5, 6, 3}

Out -

2

There are 2 N numbers 35 and 65 that may be evenly divisible by 5. Let's look at another example.

Input-

N = 1
M = 7
arr = {2, 3, 4, 5, 6, 7, 8}

Output-

1

Only one 1-digit number in the given array is divisible by 5 . Therefore, our task is to find the number of numbers that are divisible by 5 given N numbers.

The number must end with the digit 0 or 5 to be divisible by 5. Let’s see the algorithm

Algorithm

• Checks for 0 and 5 in the given array. 2. If there are both 0 and 5, there are two ways to put the number into the ones place. Otherwise, there would be a way to place the numbers.
  • Initialize the count to 2.
  • Now, the remaining positions can have m - 1, m - 2, m - 3, ... n ways to fill them respectively.
  • Write a loop that iterates from 0 to n - 1.
    • Reduce the array.
    • Multiply it with the count.
• If you have the single digit 0 or 5, there is only one way to put the number into the ones place.
  • Initialize the count to 2.
  • Now, the remaining positions can have m - 1, m - 2, m - 3, ... n ways to fill them respectively.
  • Write a loop that iterates from 0 to n - 1.
    • Reduce the array.
    • Multiply it with the count.
• If there is no number 0 or 5, then we can form a number that is divisible by 5. Returns -1 at this time.

Implementation

The following is the C implementation of the above algorithm

#include <bits/stdc++.h>

using namespace std;

int numbers(int n, int m, int arr[]) {
   bool isZeroPresent = false, isFivePresent = false;
   int numbersCount = 0;
   if (m < n) {
      return -1;
   }
   for (int i = 0; i < m; i++) {
      if (arr[i] == 0) {
         isZeroPresent = true;
      }
      if (arr[i] == 5) {
         isFivePresent = true;
      }
   }
   if (isZeroPresent && isFivePresent) {
      numbersCount = 2;
      for (int i = 0; i < n - 1; i++) {
         m--;
         numbersCount = numbersCount * m;
      }
   } else if (isZeroPresent || isFivePresent) {
      numbersCount = 1;
      for (int i = 0; i < n - 1; i++) {
         m--;
         numbersCount = numbersCount * m;
      }
   } else {
      return -1;
   }
   return numbersCount;
}
int main() {
   int arr[] = {5, 6, 3};
   cout << numbers(2, 3, arr) << endl;
   return 0;
}

Output

If you run the above code, you will get the following results.

2

The above is the detailed content of A number of N digits composed of M numbers that is divisible by 5 written in C++. For more information, please follow other related articles on the PHP Chinese website!