Count numbers which can be constructed using two numbers - GeeksforGeeks
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.
Read full article from Count numbers which can be constructed using two numbers - GeeksforGeeks
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.
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.
Time Complexity : O(n)
Auxiliary Space : O(n)
Auxiliary Space : O(n)
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;
}