Optimal solution to find out distinct pairs of integers in a SET that sum up to an integer

Suppose we have 2 Sets {1, 1, 2, 4,  4, 5}, {1, 12, 3, 4, 3, 3}  of  non-negative integers and a summation is 6.

Now we want to compute the distinct pair of elements from these Sets which summation is 6.

From 1^st set, we found {1, 5}, {2, 4}. So the count is 2.

From 2^{nd set, we found {3, 3}, Count is 1.}

Now the problem is what's the best solution for this computation where arbitrary number of Integer elements can be present in the Set. So we've to analysis data structure and algorithm for this solution.

1. The easiest and simplest way is Brute-Force algorithm. Outer Loop  and Inner Loop to check one number with every other number  find out the pairs. In this case, Run-time would be O(n^2). Therefore, If set size is n=200, then run-time goes to approximately 40000!!! So this is not acceptable algorithm.

2. If we sort the elements in the Set using quick sort and use binary search, then run-time would be O(nlogn). The details of algorithm can be like this.

• Sort the array using quick sort.
• Loop through the array while data<=sum
• Use binary search to find out the difference i.e. sum-data in array.
• if sum-data found then  addPairList (data, sum-data).
• End Loop 
• Return the count of addPairList.

This exposition of the problem having run-time of approximately O(nlogn) can be acceptable. However the solution can be even more optimized.

3. If we can find out the pairs using just ONE loop (i.e. linear search) and avoid sorting, then run-time would be O(n). And this would be most optimized solution. To achieve this, we may use Hashing data structure. The algorithm details are given below.

• Set countPairs = 0 and initialize empty HashMap.
• Loop through the array i.e. for each data in Array.
• Check HashMap contains the key of difference for current data i.e. sum-data and it's value is 0. Because if value is greater than 0, we can assume that this data already has been used in a pair.
• If the condition is TRUE then 
• Set countPairs = countPairs + 1.
• Increment 1 into HashMap value with key sum-data.
•  Else If HashMap is NOT contains key with current data then
• Put 0 into HashMap value with key data.
• End If
• End Loop
• Return countPairs.

Using this approach, we can achieve run-time O(n). And this is far better than previous two solutions. The implementation of this technique is illustrated below with Java.

       

            public static int countPairs(int[] dataSetArray, int sum) {

  Map mapNumbers = new HashMap();
  int countPairs = 0;
  for (int data : dataSetArray) {
   if (mapNumbers.containsKey(sum - data) && mapNumbers.get(sum - data) == 0) {
    countPairs++;
    mapNumbers.put((sum - data), mapNumbers.get(sum - data) + 1);
   } else if (!mapNumbers.containsKey(data)) {
    mapNumbers.put(data, 0);
   }
  }

  return countPairs;
 }

       
 

JSF (2.X+) + Spring 4 (3.X+) Integration

Here we discover the simplest solution for JSF and Spring integration. All required details configurations with full source are available in here. We use very simple configuration. Environment details are listed below:

Environment:

1. Maven Project: maven-archetype-webapp

2. JSF 2.2 and Spring 4 [All details are in pom.xml]

3. Dynamic Web Module: 3.0

4. JSF configuration just in web.xml [see in the repository]

5. All Spring related configurations are done in class WebAppInitializer.java. And bean  is configured on SpringConfig.java which also configures the component-scan package. 

package com.component.config;

import javax.servlet.ServletContext;

import javax.servlet.ServletException;

import javax.servlet.ServletRegistration.Dynamic;

import org.springframework.web.WebApplicationInitializer;

import org.springframework.web.context.ContextLoaderListener;

import org.springframework.web.context.request.RequestContextListener;

import org.springframework.web.context.support.AnnotationConfigWebApplicationContext;

import org.springframework.web.servlet.DispatcherServlet;

public class WebAppInitializer  implements WebApplicationInitializer{

@Override

public void onStartup(ServletContext servletContext)

throws ServletException {

AnnotationConfigWebApplicationContext ctx = new AnnotationConfigWebApplicationContext();  

        ctx.register(SpringConfig.class);  

        ctx.setServletContext(servletContext);    

        servletContext.addListener(new ContextLoaderListener(ctx));

        servletContext.addListener(new RequestContextListener());

        Dynamic dynamic = servletContext.addServlet("dispatcher", new DispatcherServlet(ctx));  

        dynamic.addMapping("/");  

        dynamic.setLoadOnStartup(1);

}

}

package com.component.config;

import org.springframework.context.annotation.Bean;

import org.springframework.context.annotation.ComponentScan;

import org.springframework.context.annotation.Configuration;

import com.component.dao.UserManagementDao;

import com.component.dao.UserManagementDaoImpl;

import com.service.StudentService;

import com.service.StudentServiceImpl;

@Configuration

@ComponentScan("com.component")

public class SpringConfig {

@Bean

public StudentService studentService() {

return new StudentServiceImpl();

}

}

Bean classes are very simple POJO.

package com.service;

public interface StudentService {

String getStudent(Integer id);

}

package com.service;

import java.util.HashMap;

import java.util.Map;

public class StudentServiceImpl implements StudentService {

Map<Integer, String> map = new HashMap<Integer, String>();

{

map.put(1, "Ashik");

map.put(2, "Ibraim Khan");

map.put(3, "Muhammad Ashik Ali Khan");

}

@Override

public String getStudent(Integer id) {

return map.get(id);

}

}

6. For Spring Addition Just add the following entry in faces-config.xml. 

<application>

   <el-resolver>
        org.springframework.web.jsf.el.SpringBeanFacesELResolver

   </el-resolver>

</application>

7. JSF managed beans are under component-scan package [com.component].

8. All JSF pages [*.xhtml] loads text (both regular and parameterized) from messages.properties created under package com.jsf.properties in resources [src/main/resource] folder.

header=Welcome to JSF framework integration with Spring framework

greeting_text=Welcome to JSF Framework

project_type=JSF integration with Spring

greeting_custom=Welcome to {0} for our framework

index_command=Type Name and Click

std_id=Enter Student Id:

std_name=Student Name: {0}

usr_id=Enter User Id:

usr_name=User Name: {0}

9. Java: SE 7

10. Application Server: JBOSS EAP 6.3

11. Eclipse Luna (4.4.0) or above.

Project File Structure:

Now, we create a very simple JSF page (student.xhtml) under webapp folder.

Here,

student.xhtml --> Input : ID [Integer] --> Managed Bean: StudentBean.java

result.xhtml--> Output: Name [String] --> Managed Bean: StudentBean.java

So, StudentBean.java [JSF managed bean] is very important. It is under hierarchy of component-scan package [com.component]. It links the bean StudentService by @Autowired annotation and declare it as a component i.e. @Component of spring framework.

1. It [StudentBean.java] takes the value of ID from JSF [student.xhtml],

2. passes the value to spring bean [StudentService] to retrieve the student name.

3. sets the value to bean property i.e. name. And continues the page to another with that value.

Now take a look of StudentBean.java.

package com.component.bean;

import javax.faces.bean.ManagedBean;

import javax.faces.bean.RequestScoped;

import org.springframework.beans.factory.annotation.Autowired;

import org.springframework.stereotype.Component;

import com.service.StudentService;

@ManagedBean(name="studentBean")

@RequestScoped

@Component

public class StudentBean {

@Autowired

public StudentService studentService;

private String name;

private Integer id;

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

public Integer getId() {

return id;

}

public void setId(Integer id) {

this.id = id;

}

public String showResult(){

name = studentService.getStudent(id);

return "result";

}

}

Moreover, Two JSF pages (student.xhtml & result.xhtml) are shown below.

<?xml version="1.0" encoding="ISO-8859-1" ?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html  xmlns="http://www.w3.org/1999/xhtml"

xmlns:f="http://java.sun.com/jsf/core"

    xmlns:h="http://java.sun.com/jsf/html"

    xmlns:c="http://java.sun.com/jsf/composite"

    xmlns:fac="http://java.sun.com/jsf/facelets">

<head>

<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1" />

<title>JSF 2 + Spring 4 Integration</title>

<f:loadBundle var="mymsg" basename="com.jsf.properties.messages"/>

</head>

<body>

<h:form>

<h:outputText value="#{mymsg.std_id}"/>

<h:inputText value="#{studentBean.id}"/>

<h:commandButton value="Show Name" action="#{studentBean.showResult}"/>

</h:form>

</body>

</html>

<?xml version="1.0" encoding="ISO-8859-1" ?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html  xmlns="http://www.w3.org/1999/xhtml"

xmlns:f="http://java.sun.com/jsf/core"

    xmlns:h="http://java.sun.com/jsf/html"

    xmlns:c="http://java.sun.com/jsf/composite"

    xmlns:fac="http://java.sun.com/jsf/facelets">

<head>

<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1" />

<title>JSF 2 + Spring 4 Integration</title>

<f:loadBundle var="mymsg" basename="com.jsf.properties.messages"/>

</head>

<body>

<h3>

<h:outputFormat value="#{mymsg.std_name}">

<f:param value="#{studentBean.name}"/>

</h:outputFormat> 

</h3>

</body>

</html>

 Sample Input:

Sample Output:

N.B.: This is not research but only discover of framework. Feel free to contact if any problem occurs to test this example.