Tutorialspoint.dev

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<bits/stdc++.h>
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<bool> 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

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

<?php
// PHP 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.
function 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 = array_fill(0, $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
    $result = 0;
  
    // Traverse all numbers and increment
    // result if a number can be formed 
    // using x and y.
    for ($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
$n = 15;
$x = 5;
$y = 7;
echo countNums($n, $x, $y);
  
// This code is contributed by mits
?>


Output :

6

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

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter