## Sunday, November 27, 2016

### Count numbers which can be constructed using two numbers - GeeksforGeeks

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.

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)

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