Finding binomial coefficient

Today we will learn how to find the binomial coefficient of a number

since we know

Hence we will make use of this and will find the solution recursively

#include <iostream>

#include <vector>

using namespace std;

unsigned int bin (int n, int k, vector<vector<int> > table)

{

cout<<"\n n="<<n<<"\t k="<<k;

if (n==0)

return 0;

if (!table[n-1][k-1])

table[n-1][k-1] = bin (n-1, k-1, table);

if (!table[n-1][k])

table[n-1][k] = bin (n-1, k, table);

return table[n-1][k-1] + table[n-1][k];

}

int main() {

int n, k;

cin>>n>>k;

std::vector <std::vector<int> > table (

n+1,

std::vector<int> (k+1));

for (int i=0;i<=n ;i++)

table[i][0] = 1;

cout<<bin (n,k, table);

return 0;}

Checking whether a sum exists in array by adding two numbers

Given an array we need to find whether any two numbers in the array add up to the number given

Say the array is

{23,45,34,12,78} and number given is 57.This is possible as 45+12 add up to give 57.

Simple solutions is to use brute force technique.We will see how to solve this is lesser time complexity.

//Given an array and a sum N
int isSumExists (vector<int>a, int N)
{

     int i = 0, j = a.size() - 1;

     //sort the array
     sort (a.begin(), a.end());

     for (int i=0; i<a.size(); i++) {

            //if sum present return 1
            if (a[i] + a[j]   == N)    return 1;
            else if (a[i] + a[j] < N) i++;
            else  j--;
     }

      //control will reach here if sum is not found
      return 0;
}

Numbers ending in 3 have at least one multiple having all ones. for eg., 3 and 13 have amultiples like 111 and 111111 respectively. Given such a no. , find the smallest such multiple of that number

A straight approach would be to check 11, 111, 1111 and so on to be divisible by that number.But that will not be optimal.

Let's say we have a series M(n) which is 11, 111, 1111 and so on.

So M(1) = 11, M(2) = 111 , etc

and lets assume the number we need to check the divisibility is n.

If M(i) mod n = 0, then you're done (M(i) is the answer), so let's assume it's not.

You want to find M(i+1) mod n.

Since M(i+1) = 10 * M(i) + 1, you can easily calculate

M(i+1) mod n =  (10 * (M(i) mod n) + 1) mod n

Hence the code

int count=1, rem=1;
while(rem)
{

rem= (rem*10+1)%n;

count++;
}

while(count--)
{
cout<<"1";
}