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;}