Largest multiple of 3

Given an array of digits,the task is to find the largest multiple of 3 that can be formed from array elements.

Example-

Input array is {4,8,0}.Then,the largest number formed using these digits and divisible by 3 is 840.

Properties of multiples of 3-

1.Sum of the digits of the multiple is divisible by 3.

Example-

840 is divisible by 3 and (8+4+0=12) is also divisible by 3.

2.We get the same remainder when we divide the number and sum of digits of the number by 3.

Example-

841 when divided by 3 gives remainder 1.
(8+4+1=13) when divided by 3 also gives remainder 1.

Naive Algorithm-

Generate all the combinations of the given digits and maximum of the numbers which is divisible by 3 is the result.
But,it will have a time complexity of O(2^n).

Efficient Algorithm-

1.Sort the array in increasing order.
2.Queue q0 stores the elements which on dividing by 3 gives remainder 0.
3.Queue q1 stores the elements which on dividing by 3 gives remainder 1.
4.Queue q2 stores the elements which on dividing by 3 gives remainder 2.
5.Find the sum of all the given digits.Let it be ‘s’.
6.If s is divisible by 3,goto step 9.
7.If s when divided by 3 gives remainder 1:
Remove one item from q1.
If q1 is empty,remove two items from q2.
If q2 contains less than two elements,number is not possible.
8.If s when divided by 3 gives remainder 2:
Remove one item from q2.
If q2 is empty,remove two items from q1.
If q1 contains less than two elements,number is not possible.
9.Empty all queues into an temporary array and sort it in decreasing order.

Code-

[cpp]
//a[] is the input array
//s is the sum of the digits
//n is the number of digits in the given array

#include<stdio.h>
#include<algorithm>
#include<queue>
int main()
{
using namespace std;
int i,n,s,a[1000],p[1000],w,z;
queue<int> q0;
queue<int> q1;
queue<int> q2;

scanf(“%d”,&n);s=0;
//taking the input
for(i=0;i<n;i++)
{
scanf(“%d”,&a[i]);
s=s+a[i];
}
sort(a,a+n);
for(i=0;i<n;i++)
{
if(a[i]%3==0) q0.push(a[i]);
else if(a[i]%3==1) q1.push(a[i]);
else q2.push(a[i]);
}
if(s%3==1)
{
// either remove one item from queue1
if ( !q1.empty() )
q1.pop();

// or remove two items from queue2
else
{
if ( !q2.empty() )
q2.pop();
else printf(“No number can be formed\n”);
if ( !q2.empty() )
q2.pop();
else printf(“No number can be formed\n”);
}
}
else if ((s% 3) == 2)
{
// either remove one item from queue2
if ( !q2.empty() )
q2.pop();

// or remove two items from queue1
else
{
if ( !q1.empty() )
q1.pop();
else
printf(“No number can be formed\n”);

if ( !q1.empty() )
q1.pop();
else
printf(“No number can be formed\n”);
}
}
//emptying all the queues
w=0;
while(!q0.empty())
{
z=q0.front();
p[w++]=z;
q0.pop();
}
while(!q1.empty())
{
z=q1.front();
p[w++]=z;
q1.pop();
}
while(!q2.empty())
{
z=q2.front();
p[w++]=z;
q2.pop();
}
sort(p,p+w);
//printing in descending order
for(i=w-1;i>=0;i–)
printf(“%d”,p[i]);
return 0;
}

[/cpp]

Android development primer: Progress Dialog in Android – Spinner Style

I have already posted about the Alert Dialog and the Custom Dialog in Android. However, in this post, I will show you how to make your application fancier by adding Progress Dialog in it. What is a Progress Dialog? It is a dialog that shows the user how much of the current work, if any being performed, is complete. Below is an image that shows exactly what one looks like in an Eclair emulator.

Progress1

Want to have one of these in your application? Open up an activity and start programming. Complete Source Code is at the bottom.

  • Set the content view of the activity. Make sure the layout of the activity contains a button so that the Progress Dialog can be triggered on the click of the button.
  • After setting the content view, declare and define the button in the java file.
  • Add the Progress Dialog hereafter, using the following code.
    [java]
    final ProgressDialog pd = new ProgressDialog(this);
    pd.setProgressStyle(ProgressDialog.STYLE_SPINNER);
    pd.setMessage(“Working…”);
    pd.setIndeterminate(true);
    pd.setCancelable(true);
    [/java]

    We will not be defining the Progress Dialog inside the onClick() method of the button so that we can use this dialog in other places, if need be.

  • Set up the onClickListener() and within it the onClick() methods. Inside the onClick() method, write the following code.
    [java]
    pd.show();
    [/java]

    All we need to do is to show the dialog.

  • Save your work and execute on an emulator/device.

Understanding the Code

Here I provide a little explanation as to what some of the functions in the declaration of the Progress Dialog are doing.

  • setProgressStyle() : This defines the style in which the progress will be shown. This can take one of two values – Spinner or Horizontal. Both have their own set of values in the methods described below. I will discuss the Horizontal style in the next post.
  • setMessage() : Quite obviously, it defines the message shown to the user while the Progress Dialog is displayed.
  • setIndeterminate() : This defines whether the Progress Dialog is an ongoing percentage thing. It takes a boolean value as an argument. A value of true means that it will end once the work being done ends. At this time the dialog disappears. A value of false means we will be displaying details about the progress in percentage.
  • setCancelable() : It tells the application whether the user can cancel the progress by pressing the back button. It again takes a boolean value as an argument.

COMPLETE SOURCE CODE

MainActivity.java

[java]
package com.nero.myfirstapp;

import android.os.Bundle;
import android.app.Activity;
import android.app.AlertDialog;
import android.app.Dialog;
import android.app.ProgressDialog;
import android.content.DialogInterface;
import android.content.Intent;
import android.view.LayoutInflater;
import android.view.Menu;
import android.view.MenuItem;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
import android.widget.Toast;

public class Main extends Activity {

@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
Button but = (Button) findViewById(R.id.but);
final ProgressDialog pd = new ProgressDialog(Main.this);
pd.setProgressStyle(ProgressDialog.STYLE_SPINNER);
pd.setMessage(“Working…”);
pd.setIndeterminate(true);
pd.setCancelable(true);

but.setOnClickListener(new OnClickListener() {

@Override
public void onClick(View arg0) {
// TODO Auto-generated method stub
pd.show();
}

});

}
}

[/java]

Remember that the spinner in this dialog will keep spinning as we have not defined any action that needs to be completed. Hence you must hit the back button to end it.

Android development primer: Creating Dialogs in Android

We have seen how to create and use Alert Dialog. Now we will see how to create and use a general dialog. In most places you find Alert Dialog explained on after they have given you a basic tutorial about Dialogs, their creation and use. However since Alert Dialog is a complete predefined element of Android, I chose to give you the tutorial earlier so that the learning curve for you remains smooth.

Here we will create a dialog, a layout for it and display it in an activity. Complete Source Code is at the bottom.

  • Navigate to <yourpackagename> -> res -> layout.
  • Create an XML, pick up a layout for it and name it according to your choice. We will use this layout for the dialog.
  • I will just have a button and a text view in the dialog. You can follow along or you can become creative and add more elements. Write the following code in the dialog
    <?xml version="1.0" encoding="utf-8"?>
    <RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
        android:layout_width="match_parent"
        android:layout_height="match_parent" >
    
        <TextView
            android:id="@+id/textView1"
            android:layout_width="match_parent"
            android:layout_height="wrap_content"
            android:layout_alignParentTop="true"
            android:layout_centerHorizontal="true"
            android:text="This is a test dialog"
            android:textAppearance="?android:attr/textAppearanceMedium" 
            android:paddingBottom="10sp"/>
    
        <Button
            android:id="@+id/button1"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:layout_below="@+id/textView1"
            android:layout_centerHorizontal="true"
            android:text="Button" />
    
    </RelativeLayout>
  • Now in the activity I have a button that triggers the dialog on the click. Add the following code to the onClick() method of the onClickListener() constructor.
    [java]
    final Dialog d = new Dialog(Main.this);
    d.setContentView(R.layout.dialog);
    Button tempbut = (Button) d.findViewById(R.id.button1);
    tempbut.setOnClickListener(new OnClickListener() {

    @Override
    public void onClick(View v) {
    // TODO Auto-generated method stub
    d.dismiss();
    }
    });
    d.setTitle(“Test Dialog”);
    d.show();
    [/java]

  • Save it and execute it on the emulator/device.

dialog

This is how it looks on my Eclair emulator. Clicking the button will dismiss the dialog. This has been defined in the dialog code. Take some time to go through the code you have just added. It is very simple but nonetheless important.

COMPLETE SOURCE CODE

dialog.xml

<?xml version="1.0" encoding="utf-8"?>
<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    android:layout_width="match_parent"
    android:layout_height="match_parent" >

    <TextView
        android:id="@+id/textView1"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:layout_alignParentTop="true"
        android:layout_centerHorizontal="true"
        android:text="This is a test dialog"
        android:textAppearance="?android:attr/textAppearanceMedium" 
        android:paddingBottom="10sp"/>

    <Button
        android:id="@+id/button1"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_below="@+id/textView1"
        android:layout_centerHorizontal="true"
        android:text="Button" />

</RelativeLayout>

activity_main.xml

<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:paddingBottom="@dimen/activity_vertical_margin"
    android:paddingLeft="@dimen/activity_horizontal_margin"
    android:paddingRight="@dimen/activity_horizontal_margin"
    android:paddingTop="@dimen/activity_vertical_margin"
    tools:context=".Main" >

    <Button
        android:id="@+id/but"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:layout_alignParentBottom="true"
        android:layout_alignParentLeft="true"
        android:text="Button" />

</RelativeLayout>

MainActivity.java

[java]
package com.nero.myfirstapp;

import android.os.Bundle;
import android.app.Activity;
import android.app.AlertDialog;
import android.app.Dialog;
import android.content.DialogInterface;
import android.content.Intent;
import android.view.LayoutInflater;
import android.view.Menu;
import android.view.MenuItem;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
import android.widget.Toast;

public class Main extends Activity {

@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
Button but = (Button) findViewById(R.id.but);
but.setOnClickListener(new OnClickListener() {

@Override
public void onClick(View v) {
final Dialog d = new Dialog(MainActivity.this);
d.setContentView(R.layout.dialog);
Button tempbut = (Button) d.findViewById(R.id.button1);
tempbut.setOnClickListener(new OnClickListener() {

@Override
public void onClick(View v) {
// TODO Auto-generated method stub
d.dismiss();
}
});
d.setTitle(“Test Dialog”);
d.show();
}
});

}
}

[/java]

Fibonacci Numbers

Fibonacci is the most famous sequence in the programming world.
It is defined by the following recursive formulation:
f(n)=f(n-1) + f(n-2) where f(0)=0 & f(1)=1.
The first few numbers of the sequence are:
0,1,1,2,3,5,8,13,21,34,55……
Program to find the N-Th Fibonacci number can be implemented iteratively or recursively very easily.But,for large values of N,we need an optimized algorithm.

Using Recursion-

[cpp]
fib(n)
{
if(n==0) return 0;
if(n==1) return 1;
return fib(n-1)+fib(n-2);
}
[/cpp]

This has an exponential time complexity.

Using Iteration-

[cpp]
fib(n)
{
if(n==0) return 0;
if(n==1) return 1;
a=0;
b=1;
for(i=2;i<=n;i++)
{
c=a+b;
a=b;
b=c;
}
return b;
}
[/cpp]

This code has a time complexity of O(N).

Using power of the matrix{(0,0),(1,1)}-

If we n times multiply the matrix M = {{1,1},{1,0}} to itself,then we get the (n+1)th Fibonacci number as the element at row and column (0, 0) in the resultant matrix.

|1 1|^n = | F(n+1) F(n) |
|0 1|        | F(n)   F(n-1)|

Result of exponentiation can be calculated using this method in O(logn).

[cpp]
/* function that returns nth Fibonacci number */
int fib(int n)
{
int F[2][2] = {{1,1},{1,0}};
if(n == 0)
return 0;
power(F, n-1);
return F[0][0];
}

/* Optimized version of calculating power*/
void power(int F[2][2], int n)
{
if( n == 0 || n == 1)
return;
int M[2][2] = {{1,1},{1,0}};

power(F, n/2);
multiply(F, F);

if( n%2 != 0 )
multiply(F, M);
}

void multiply(int F[2][2], int M[2][2])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];

F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
[/cpp]

This code has a time complexity of O(logN).

BFS & DFS

A traversal is a systematic walk which visits the nodes of the graph in a specific order.
Two Types:-
1.Breadth First Traversal
2.Depth First Traversal

Breadth First Traversal-

It traverses the successors of the start node,generation after generation in a horizontal or linear fashion.

Algorithm-

BFT(s)
{
//s is the start vertex of the traversal in an undirected graph G.
//Q is a queue which keeps track of the vertices whose adjacent nodes are to be visited.
//Vertices which have been visited have their ‘visited’ flags set to 1.
//Initially,visited(vertex) = 0 for all vertices of graph G.
//queue is a linear list in which all insertions are made at one end and all deletions are made at the other end.

Initialize queue Q;

visited(s)=1;

ENQUEUE (Q,s) //insert s into queue Q

while (Q is not empty) //process until Q is empty
{
DEQUEUE(Q,s) //delete s from Q

print (s); //output the vertex visited.

for all vertices v adjacent to s
{
if(visited[v]=0)
{
ENQUEUE(Q,v);
visited(v)=1;
}
}
}
}

Code-

[cpp]
vector<int>a[1005];
int visited[1000]={0};
//N is the number of nodes and M is the number of edges
//preparing adjacency list
for(i=0;i<M;i++)
{
scanf(“%d %d”,&x,&y);
a[x].push_back(y);
}
queue<int> q;
visited[s]=1;
q.push(s);
while(!q.empty())
{
s=q.front();
//retrieving the element which is to be deleted.
printf(“%d “,s);
q.pop();
//checking vertices adjacent to s
for(int i=0;i<a[s].size();i++)
{
if(visited[a[s][i]]==0)
{
visited[a[s][i]]=1;
q.push(a[s][i]);
}
}
}
[/cpp]

Depth First Traversal-

This traversal visits each node,that is,the first occurring among its adjacent nodes and successively repeats the operation,thus moving deeper and deeper into the graph.In contrast,BFT moves side ways or breadth ways in the graph.

Algorithm-

DFT(s)
{
// s is the start vertex
visited(s)=1;
print (s);
for each vertex v adjacent to s
{
if( visited(v)=0 ) {DFT(v);}
}
}

Code-

[cpp]
vector<int>a[1005];
int visited[1000]={0};
//N is the number of nodes and M is the number of edges
//preparing adjacency list
for(i=0;i<M;i++)
{
scanf(“%d %d”,&x,&y);
a[x].push_back(y);
}
for(int i=0;i<N;i++)
{
if(visited[i]==0)
{
dfs(i);
}
}
void dfs(int node)
{
visited[node]=1;

printf(“%d “,node);

for(int i=0;i<a[s].size();i++)
{
if(visited[a[s][i]]==0)
{
dfs(a[s][i]);
}
}
}

[/cpp]

NOTE-

If an adjacency matrix is used to represent the graph,the time complexity in both the traversals will be O(N^2). But,the use of adjacency list results in a time complexity of O(N).

All about Factorial(!)

In mathematics,the factorial of any positive number N is the product of the positive integers less than or equal to N.It is denoted by ‘N!’.

Example-

5!= 5*4*3*2*1 =120
Also,0!=1.

In C/C++,no data type can store the value of factorial of a number greater than 20.To find the factorial of greater numbers easily,JAVA/Python can be used.

JAVA Code-

This code uses BigIntegers.

[cpp]
import java.io.*;
import java.math.BigInteger;
public class Main
{
public static void main(String[] args) throws IOException
{
String n;
BufferedReader d= new BufferedReader(new InputStreamReader(System.in));
n=d.readLine();
int y=Integer.parseInt(n);
BigInteger x=new BigInteger(n); //converting string to biginteger
for(int j=y-1;j>=1;j–)
{
String str= Integer.toString(j);
x=x.multiply(new BigInteger(str));
}
System.out.println(x);
}
}
[/cpp]

Length of the factorial-

The number of digits in N! is approximately:-
[(log(2*pie*n)/2)+n*(log(n)-1))/log(10)]+1;

Stirling’s approximation-

N! is approximately equal to {sqrt(2*pie*n)}*{(n/e)^n}.

To find the power of a prime factor of N! –

Let the prime factor be X.Then,the power of X will be :-

[N/X]+[N/(X^2)]+[N/(X^3)]+….. where [.] denotes the greatest integer function.

For example-

Power of 2 in 5! will be-

[5/2]+[5/4]+[5/8]+[5/16]+…..
=> 2+1+0+0+….
which is equal to 3.

Also,5!=2^3 * 3^1 * 5^1

To find the number of zeroes at the end of N!-

Find the power of 2 and 5 in N!(Since,10=5*2).
Let it be ‘v’ and ‘s’ respectively.
if(v<=s),then number of zeroes at the end is ‘v’,else,’s’.

Code-

[cpp]
//initialization
s=0;
v=0;

p=N; //copying value of N to another variable
//Finding power of 5
while(N>0)
{
q=N/5;
s=s+q;
N=q;
}
//Finding power of 2
while(p>0)
{
w=p/2;
v=v+w;
p=w;
}

if(v>=s) printf(“%d\n”,s);
else printf(“%d\n”,v);
}
[/cpp]

Last Non-zero digit of the factorial-

Lets say D(N) denotes the last non zero digit of factorial, then the algo says:-
If tens digit of N is odd,D(N)=4*D[N/5]*D(Unit digit of N)
If tens digit of N is even,D(N)=6*D[N/5]*D(Unit digit of N)
where [N/5] is greatest Integer Function.

Example-

D(26)=6*D[26/5]*D(6)=6*D(5)*D(6)=6*2*2=4
[D(5) means last non zero digit of 5!=120 which is 2, same for D(6)]

Android development primer: Creating layouts for Alert Dialog

Don’t like the traditional way in which the Alert Dialog appears? Would you rather have a custom layout for it? Well, not a problem at all. In this post I will show you exactly how to do that. I would like you to know that there are other types of Dialogs that you can have. You can have custom layouts for each of them too. You could customize dialogs to contain EditTexts and take inputs from the user.
Complete Source Code is at the bottom.

So open up an activity and start coding.

  • First of all we will create a layout for our Dialog. So navigate to <yourprojectname> -> res -> layout. Create a new XML file and choose the type of layout you want.
  • Here I will insert two EditTexts in the Alert Dialog. You can follow along or create your own custom layout.Write in the following code into your XML file.
    <?xml version="1.0" encoding="utf-8"?>
    <RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
        android:layout_width="match_parent"
        android:layout_height="match_parent" >
    
        <EditText
            android:id="@+id/editText1"
            android:layout_width="match_parent"
            android:layout_height="wrap_content"
            android:layout_alignParentLeft="true"
            android:layout_alignParentTop="true"
            android:ems="10" >
    
            <requestFocus />
        </EditText>
    
        <EditText
            android:id="@+id/editText2"
            android:layout_width="match_parent"
            android:layout_height="wrap_content"
            android:layout_alignParentLeft="true"
            android:layout_below="@+id/editText1"
            android:ems="10" />
    
    </RelativeLayout>
  • Now that we have the layout ready, we will need to refer to it from our java code. Go to the concerned activity and make sure you have a way to trigger the dialog, for e.g. a Button. I have a button and I will trigger the Alert Dialog at the click of the button.
  • Write the following code in the onClick() function inside the onClickListener() constructor.
    [java]
    LayoutInflater lf = LayoutInflater.from(Main.this);
    final View DialogView = lf.inflate(R.layout.dialog, null);
    AlertDialog.Builder alert = new AlertDialog.Builder(Main.this);
    alert.setTitle(“Test Alert Dialog”).setView(DialogView).setMessage(msg).setPositiveButton(“Yes”,
    new DialogInterface.OnClickListener() {

    @Override
    public void onClick(DialogInterface dialog, int which) {
    Toast.makeText(getApplicationContext(), “Yes”, Toast.LENGTH_LONG).show();
    }
    }).setNegativeButton(“No”,
    new DialogInterface.OnClickListener() {

    @Override
    public void onClick(DialogInterface dialog, int which) {
    Toast.makeText(getApplicationContext(), “No”, Toast.LENGTH_LONG).show();
    }
    });
    alert.show();

    [/java]

  • For now it will be enough for you to know that LayoutInflater is used to inflate or in simple terms set the layout of a View. I will discuss it in a later post.
  • If you have read my previous post, you will notice that there is only a slight change in the code for the AlertDialog. We are now also using a function setView() here. It’s name reflects exactly what it is used for. This is the way we can force an AlertDialog to possess a design/layout of our choice.
  • Save everything and execute it on an emulator/device.

layoutalert

Here’s how it looks like on my Eclair emulator. You can choose to have different background color for the dialog, add more fields etc.

COMPLETE SOURCE CODE

dialog.xml

<?xml version="1.0" encoding="utf-8"?>
<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    android:layout_width="match_parent"
    android:layout_height="match_parent" >

    <EditText
        android:id="@+id/editText1"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:layout_alignParentLeft="true"
        android:layout_alignParentTop="true"
        android:ems="10" >

        <requestFocus />
    </EditText>

    <EditText
        android:id="@+id/editText2"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:layout_alignParentLeft="true"
        android:layout_below="@+id/editText1"
        android:ems="10" />

</RelativeLayout>

activity_main.xml

<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:paddingBottom="@dimen/activity_vertical_margin"
    android:paddingLeft="@dimen/activity_horizontal_margin"
    android:paddingRight="@dimen/activity_horizontal_margin"
    android:paddingTop="@dimen/activity_vertical_margin"
    tools:context=".Main" >

    <Button
        android:id="@+id/but"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:layout_alignParentBottom="true"
        android:layout_alignParentLeft="true"
        android:text="Button" />

</RelativeLayout>

MainActivity.java

[java]
package com.nero.myfirstapp;

import android.os.Bundle;
import android.app.Activity;
import android.app.AlertDialog;
import android.content.DialogInterface;
import android.content.Intent;
import android.view.LayoutInflater;
import android.view.Menu;
import android.view.MenuItem;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
import android.widget.Toast;

public class Main extends Activity {

@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
Button but = (Button) findViewById(R.id.but);
final String msg=”This is a test Alert Dialog Box”;

but.setOnClickListener(new OnClickListener() {

@Override
public void onClick(View v) {
LayoutInflater lf = LayoutInflater.from(MainActivity.this);
final View DialogView = lf.inflate(R.layout.dialog, null);
AlertDialog.Builder alert = new AlertDialog.Builder(Main.this);
alert.setTitle(“Test Alert Dialog”).setView(DialogView).setMessage(msg).setPositiveButton(“Yes”,
new DialogInterface.OnClickListener() {

@Override
public void onClick(DialogInterface dialog, int which) {
Toast.makeText(getApplicationContext(), “Yes”, Toast.LENGTH_LONG).show();
}
}).setNegativeButton(“No”,
new DialogInterface.OnClickListener() {

@Override
public void onClick(DialogInterface dialog, int which) {
Toast.makeText(getApplicationContext(), “No”, Toast.LENGTH_LONG).show();
}
});
alert.show();
}
});

}
}

[/java]

Android development primer: Creating Alert Dialogs in Android

In Android devices, probably the thing that we come across most frequently is Alert Dialog Boxes. If you are not familiar with an Alert Dialog Box, here’s what it looks like on an Eclair emulator.

alert1

You should know that the Dialog’s title, text and the buttons are customizable and can be made to read anything.
We’ll see how to do it in a minute. So open an activity and start coding. Complete Source Code is at the bottom.

  • For the layout of the activity insert a button. We will make the Alert Dialog appear when the button is pressed.
  • Set the content view of the Activity and add declare the button from the layout in the java file.
  • We will now set the onClickListener() attribute of the button. Write the following code in the onClick() function of the onClickListener() attribute.
    [java]
    AlertDialog.Builder alert = new AlertDialog.Builder(Main.this);
    alert.setTitle(“Test Alert Dialog”).setMessage(msg).setPositiveButton(“Yes”,
    new DialogInterface.OnClickListener() {

    @Override
    public void onClick(DialogInterface dialog, int which) {
    Toast.makeText(getApplicationContext(), “Yes”, Toast.LENGTH_LONG).show();
    }
    }).setNegativeButton(“No”,
    new DialogInterface.OnClickListener() {

    @Override
    public void onClick(DialogInterface dialog, int which) {
    Toast.makeText(getApplicationContext(), “No”, Toast.LENGTH_LONG).show();
    }
    });
    alert.show();
    [/java]

  • If it is not clear have a look at the complete Source Code at the bottom to understand what you need to do.
  • If you take some time and go through the AlertDialog code snippet, you can see that the components used in it are quite mnemonic. The functions such as setTitle()setMessage()setPositiveButton()setNegativeButton() represent exactly what they do. However in case you have an issue understanding them, drop a comment and I will explain it the best I can.
  • Save the activity and execute in an emulator/device.
  • Below images shows the results of clicking the Yes and No button on the Alert Dialog respectively.

alert2   alert3

COMPLETE SOURCE CODE

activity_main.xml

<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:paddingBottom="@dimen/activity_vertical_margin"
    android:paddingLeft="@dimen/activity_horizontal_margin"
    android:paddingRight="@dimen/activity_horizontal_margin"
    android:paddingTop="@dimen/activity_vertical_margin"
    tools:context=".Main" >

    <Button
        android:id="@+id/but"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:layout_alignParentBottom="true"
        android:layout_alignParentLeft="true"
        android:text="Button" />

</RelativeLayout>

Main.java

[java]
package com.nero.myfirstapp;

import android.os.Bundle;
import android.app.Activity;
import android.app.AlertDialog;
import android.content.DialogInterface;
import android.content.Intent;
import android.view.Menu;
import android.view.MenuItem;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
import android.widget.Toast;

public class Main extends Activity {

@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
Button but = (Button) findViewById(R.id.but);
final String msg=”This is a test Alert Dialog Box”;
but.setOnClickListener(new OnClickListener() {

@Override
public void onClick(View v) {
AlertDialog.Builder alert = new AlertDialog.Builder(Main.this);
alert.setTitle(“Test Alert Dialog”).setMessage(msg).setPositiveButton(“Yes”,
new DialogInterface.OnClickListener() {

@Override
public void onClick(DialogInterface dialog, int which) {
Toast.makeText(getApplicationContext(), “Yes”, Toast.LENGTH_LONG).show();
}
}).setNegativeButton(“No”,
new DialogInterface.OnClickListener() {

@Override
public void onClick(DialogInterface dialog, int which) {
Toast.makeText(getApplicationContext(), “No”, Toast.LENGTH_LONG).show();
}
});
alert.show();
}
});

}

@Override
public boolean onCreateOptionsMenu(Menu menu) {
// Inflate the menu; this adds items to the action bar if it is present.
getMenuInflater().inflate(R.menu.main, menu);
return true;
}
}

[/java]

Here, we are making a simple Toast appear on the Click of the Positive or the Negative button of the Alert Dialog. Once you are into making complex applications, you will be doing much more than this with the Alert Dialog.

Binomial Coefficient

Binomial Coefficient is represented by nCk which means number of ways of choosing k objects from n objects.It is the coefficient of x^k term in the polynomial expansion of (1+x)^n.It also represents an entry in Pascals Triangle.

Properties-

1. nCk=(n!)/[(k!)*(n-k)!]
2. nCn=1
3. nC0=1
4. nCk=(n-1)C(k)+(n-1)C(k-1)
5. nCk=(n)C(n-k)

The task is to find the value of nCk given the values of n and k.

Recursive solution-

[cpp]
int binomialCoeff(int n, int k)
{
// Base Cases
if (k==0 || k==n)
return 1;

// Recurrence
return binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}
[/cpp]

For large values of n,there will be many common subproblems.For example-
To calculate 5C2,function will be called for 4C2 and 4C1.
To calculate 4C1,function will be again called for 3C0 and 3C1.
To calculate 4C2,function will be called for 3C1 and 3C2.
So,3C1 is being calculated twice.
This problem has overlapping sub-problems property.Re-computation of same sub-problems can be avoided by constructing a temporary array C[][] and storing the results like we do in other dynamic programming problems.

DP based solution-

[cpp]
//C[][] is the temp array

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

for(j=0;j<=i;j++)
{

//base condition
if((i==0)||(j==0)) C[i][j]=1;

else C[i][j]=C[i-1][j-1]+C[i-1][j];
}
}
//C[n][k] gives the result
[/cpp]

Time Complexity of this code is O(n*k).

Note-

n,k are non negative integers.
nCk is valid only for n>0 and 0<=k<=n.

Android development primer: Know the AndroidManifest.xml

Enough programming. Let’s take a break and look into one of the vital components of any Android application, the AndroidManifest.xml file. Every Android application must have an AndroidManifest.xml file with that exact name, in its root directory. It provides the Android system important information about the application you are about to run in the device.

Navigate to <yourprojectname> -> AndroidManifest.xml. I will give you a brief overview of what purpose do the various sections of the manifest serve. Some of these might not be present in your manifest file. That is because components are added in the manifest file according to the needs of the developer. Nonetheless it will do you good to know about them.

  • package : This names the package your Android Application is in. You can change this at any time you want, but it will require further changes in each java file in your application.
  • versionCode : This is the version code of your application. This is useful when you are modifying you application and want to have a clean copy of the application as another version.
  • versionName : You can also name the version of your application. Change this to your liking.
  • minSdkVersion : While creating the project you must have selected a minimum API level. Devices having android versions below this API will not be able to run your application.
  • targetSdkVersion : While creating the project you must have selected a target API level. Devices having android versions below this API (and above the minimum API level) will be able to run your application, but you have indicated that this API is the one you are particularly targeting.
  • icon : This is the icon that will appear once the application has installed in your device. You can have an image in the drawable folder and make that you application icon.
  • label : This is the name of your application. Your application will be installed in the device or uploaded to the Android market by this name. The default value is @string/app_name. I will talk about what that is and how to change it in a later post.
  • theme : This is the basic theme of your application. It is the one you selected while first creating a project.
  • activity -> name : This is the name of you activity. There will be as many activity tags in your manifest, as there are activities in your application. Each activity must be declared in the manifest, failing which your application will crash as soon as you try to navigate to an undeclared activity.
  • activity -> screenOrientation : This indicates the orientation of the screen that the developer wants his application to have. It can have two possible values – portrait and landscape. For simplicity, portrait is vertical and landscape is horizontal. These are used when you do not want to auto-rotate the screen when the device is rotated. If the screenOrientation attribute is not specified, it indicates auto-rotation of the device screen is allowed.
  • intent-filter : If you have read my previous posts, I told you that an intent is used to push the current activity into the back stack and call upon another activity. The intent filter here acts in the same way. This, by default is present in only one activity MainActivity. That is because it is the activity which is first displayed when the application is launched. Since we are not switching from one activity to another here thus the Android system’s intent is used to do this.
  • receiver : Just like there are activities in the application, it can also contain broadcast receivers.  Each broadcast receiver must be declared in the manifest.
  • uses-permission : This is an interesting component. Your application might use some data or features from the user’s device that might/might not be acceptable to the user. In order to let the user know that some specific features and data are required in order for your application to work, uses-permission is used. This informs the user, at the time of installation of the application about these requirements. It is only after the user approves, that your application will be installed.
  • It also declares the permissions other applications need in order to communicate with your application.
  • The manifest also lists the library against which the application must be linked, if any.

So, you can see that the AndroidManifest.xml file serves the most important purpose of letting the Android system and the user know about what your application needs, what it does and other vital details.
Above are the most frequently seen/used components of the android manifest file. You might come across many more as you step into advanced Android Programming.