Count numbers which can be constructed using two numbers

Given three positive integers x, y and n, the task is to find count of all numbers from 1 to n that can be formed using x and y. A number can be formed using x and y if we can get it by adding any number of occurrences of x and/or y.

Examples :

Input  : n = 10, x = 2, y = 3
Output : 9
We can form 9 out of 10 numbers using 2 and 3
2 = 2, 3 = 3, 4 = 2+2, 5 = 2+3, 6 = 3+3
7 = 2+2+3, 8 = 3+3+2, 9 = 3+3+3
and 10 = 3+3+2+2.

Input  : n = 10, x = 5, y = 7
Output : 3
We can form 3 out of 10 numbers using 5 and 7
The numbers are 5, 7 and 10

Input  : n = 15, x = 5, y = 7
Output : 6
We can form 6 out of 10 numbers using 5 and 7.
The numbers are 5, 7, 10, 12, 14 and 15.

Input  : n = 15, x = 2, y = 4
Output : 7

A simple solution is to write a recursive code that starts with 0 and makes two recursive calls. One recursive call adds x and other adds y. This way we count total numbers. We need to make sure a number is counted multiple times.

An efficient solution solution is to use a boolean array arr[] of size n+1. An entry arr[i] = true is going to mean that i can be formed using x and y. We initialize arr[x] and arr[y] as true if x and y are smaller than or equal to n. We start traversing the array from smaller of two numbers and mark all numbers one by one that can be formed using x and y. Below is the implementation.

C++

 // C++ program to count all numbers that can // be formed using two number numbers x an y #include using namespace std;    // Returns count of numbers from 1 to n that can be formed // using x and y. int countNums(int n, int x, int y) {     // Create an auxiliary array and initialize it      // as false. An entry arr[i] = true is going to      // mean that i can be formed using x and y     vector arr(n+1, false);        // x and y can be formed using x and y.     if (x <= n)         arr[x] = true;     if (y <= n)         arr[y] = true;        // Initialize result     int result = 0;        // Traverse all numbers and increment     // result if a number can be formed using     // x and y.     for (int i=min(x, y); i<=n; i++)     {         // If i can be formed using x and y         if (arr[i])         {              // Then i+x and i+y can also be formed             // using x and y.                            if (i+x <= n)                 arr[i+x] = true;             if (i+y <= n)                 arr[i+y] = true;                // Increment result              result++;         }     }     return result; }    // Driver code int main() {     int n = 15, x = 5, y = 7;     cout << countNums(n, x, y);     return 0; }

Java

 // Java program to count all numbers that can // be formed using two number numbers x an y    class gfg{ // Returns count of numbers from 1 to n that can be formed // using x and y. static int countNums(int n, int x, int y) {     // Create an auxiliary array and initialize it      // as false. An entry arr[i] = true is going to      // mean that i can be formed using x and y     boolean[] arr=new boolean[n+1];        // x and y can be formed using x and y.     if (x <= n)         arr[x] = true;     if (y <= n)         arr[y] = true;        // Initialize result     int result = 0;        // Traverse all numbers and increment     // result if a number can be formed using     // x and y.     for (int i=Math.min(x, y); i<=n; i++)     {         // If i can be formed using x and y         if (arr[i])         {              // Then i+x and i+y can also be formed             // using x and y.                          if (i+x <= n)                 arr[i+x] = true;             if (i+y <= n)                 arr[i+y] = true;                // Increment result              result++;         }     }     return result; }    // Driver code public static void main(String[] args) {     int n = 15, x = 5, y = 7;     System.out.println(countNums(n, x, y)); } } // This code is contributed by mits

Python3

 # Python3 program to count all numbers  # that can be formed using two number  # numbers x an y    # Returns count of numbers from 1  # to n that can be formed using x and y. def countNums(n, x, y):        # Create an auxiliary array and      # initialize it as false. An      # entry arr[i] = True is going to     # mean that i can be formed using     # x and y     arr = [False for i in range(n + 2)]        # x and y can be formed using x and y.     if(x <= n):         arr[x] = True     if(y <= n):         arr[y] = True        # Initialize result     result = 0        # Traverse all numbers and increment     # result if a number can be formed      # using x and y.     for i in range(min(x, y), n + 1):            # If i can be formed using x and y         if(arr[i]):                # Then i+x and i+y can also              # be formed using x and y.             if(i + x <= n):                 arr[i + x] = True             if(i + y <= n):                 arr[i + y] = True                # Increment result             result = result + 1        return result    # Driver code n = 15 x = 5 y = 7 print(countNums(n, x, y))    # This code is contributed by # Sanjit_Prasad

/div>

C#

 // C# program to count all numbers that can  // be formed using two number numbers x an y     using System;    public class GFG{     // Returns count of numbers from 1 to n that can be formed  // using x and y.  static int countNums(int n, int x, int y)  {      // Create an auxiliary array and initialize it      // as false. An entry arr[i] = true is going to      // mean that i can be formed using x and y      bool []arr=new bool[n+1];         // x and y can be formed using x and y.      if (x <= n)          arr[x] = true;      if (y <= n)          arr[y] = true;         // Initialize result      int result = 0;         // Traverse all numbers and increment      // result if a number can be formed using      // x and y.      for (int i=Math.Min(x, y); i<=n; i++)      {          // If i can be formed using x and y          if (arr[i])          {              // Then i+x and i+y can also be formed              // using x and y.                         if (i+x <= n)                  arr[i+x] = true;              if (i+y <= n)                  arr[i+y] = true;                 // Increment result              result++;          }      }      return result;  }     // Driver code      static public void Main (){         int n = 15, x = 5, y = 7;          Console.WriteLine(countNums(n, x, y));      } }

PHP



Output :

6

Time Complexity: O(n)
Auxiliary Space: O(n)

tags:

Mathematical Mathematical