A Group chat application in Java

In this post, a group chat application using MulticastSocket (Java Platform SE 7) class is discussed. A MulticastSocket is a (UDP) DatagramSocket, with additional capabilities for joining “groups” of other multicast hosts on the internet.

Implementation

import java.net.*;
import java.io.*;
import java.util.*;
public class GroupChat
{
    private static final String TERMINATE = "Exit";
    static String name;
    static volatile boolean finished = false;
    public static void main(String[] args)
    {
        if (args.length != 2)
            System.out.println("Two arguments required:
            <multicast-host> <port-number>");
        else
        {
            try
            {
                InetAddress group = InetAddress.getByName(args[0]);
                int port = Integer.parseInt(args[1]);
                Scanner sc = new Scanner(System.in);
                System.out.print("Enter your name: ");
                name = sc.nextLine();
                MulticastSocket socket = new MulticastSocket(port);
            
                // Since we are deploying
                socket.setTimeToLive(0);
                this on localhost only (For a subnet set it as 1)
                socket.joinGroup(group);
                Thread t = new Thread(new
                ReadThread(socket,group,port));
            
                // Spawn a thread for reading messages
                t.start();
                
                // sent to the current group
                System.out.println("Start typing messages...\n");
                while(true)
                {
                    String message;
                    message = sc.nextLine();
                    if(message.equalsIgnoreCase(GroupChat.TERMINATE))
                    {
                        finished = true;
                        socket.leaveGroup(group);
                        socket.close();
                        break;
                    }
                    message = name + ": " + message;
                    byte[] buffer = message.getBytes();
                    DatagramPacket datagram = new
                    DatagramPacket(buffer,buffer.length,group,port);
                    socket.send(datagram);
                }
            }
            catch(SocketException se)
            {
                System.out.println("Error creating socket");
                se.printStackTrace();
            }
            catch(IOException ie)
            {
                System.out.println("Error reading/writing from/to
                socket");
                ie.printStackTrace();
            }
        }
    }
}
class ReadThread implements Runnable
{
    private MulticastSocket socket;
    private InetAddress group;
    private int port;
    private static final int MAX_LEN = 1000;
    ReadThread(MulticastSocket socket,InetAddress group,int port)
    {
        this.socket = socket;
        this.group = group;
        this.port = port;
    }
    
    @Override
    public void run()
    {
        while(!GroupChat.finished)
        {
                byte[] buffer = new byte[ReadThread.MAX_LEN];
                DatagramPacket datagram = new
                DatagramPacket(buffer,buffer.length,group,port);
                String message;
            try
            {
                socket.receive(datagram);
                message = new
                String(buffer,0,datagram.getLength(),"UTF-8");
                if(!message.startsWith(GroupChat.name))
                    System.out.println(message);
            }
            catch(IOException e)
            {
                System.out.println("Socket closed!");
            }
        }
    }
}

Save the file as GroupChat.java and compile it using javac and then run the program using two command line arguments as specified. A multicast host is specified by a class D IP address and by a standard UDP port number. Class D IP addresses are in the range 224.0.0.0 to 239.255.255.255, inclusive. The address 224.0.0.0 is reserved and should not be used.
Here is a sample output of the above program:
multicast socket api in java

multicast socket api in java1multicast socket api in java12
We have used the multicast host IP address as 239.0.0.0 and the port number as 1234 (since the port numbers 0 through 1023 are reserved). There are 3 members in the group: Ironman, CaptainAmerica, and Groot. Start all three terminals first before sending the message, otherwise messages which are sent before starting the terminal are lost (since there is no facility of buffer incorporated to store the messages.) We need two threads in this application. One for accepting the user input (using the java.util.Scanner class) and the other for reading the messages sent from other clients. Hence I have separated the thread which does the reading work into ReadThreadclass. For leaving the group, any of the user can type in Exit to terminate the session.

The above program is executed on a single machine. Socket programming is meant for distributed programming. The same piece of code snippet when present on different machines which have Java installed can satisfy that requirement. This is just the bare bones service logic. The project would be even more fascinating if the front-end is developed. You can use Java’s AWT (Abstract Window Toolkit) or its advanced counterpart, Java Swing to develop the front end. Since this wouldn’t be part of Socket programming I’m leaving it untouched without getting into the details.
Additional points:

  • You can incorporate network security feature by performing encryption before sending the message over the network.
  • Primitive techniques such as Caesar cipher or advanced methods such as RSA can be used to perform encryption-decryption. You can try using Java’s RMI (Remote Method Invocation) to perform the same task.
  • Here, you can leverage the abstraction offered by Java to maximum extent. However, if your primary objective is efficiency, then Socket programming is the best choice. Since it doesn’t require any run time support, it is a bit faster compared to RMI.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Main thread in Java

Java provides built-in support for multithreaded programming. A multi-threaded program contains two or more parts that can run concurrently. Each part of such a program is called a thread, and each thread defines a separate path of execution.

Main Thread

When a Java program starts up, one thread begins running immediately. This is usually called the main thread of our program, because it is the one that is executed when our program begins.

Properties :

  • It is the thread from which other “child” threads will be spawned.
  • Often, it must be the last thread to finish execution because it performs various shutdown actions

Flow diagram :

main thread in java

How to control Main thread

The main thread is created automatically when our program is started. To control it we must obtain a reference to it. This can be done by calling the method currentThread( ) which is present in Thread class. This method returns a reference to the thread on which it is called. The default priority of Main thread is 5 and for all remaining user threads priority will be inherited from parent to child.

// Java program to control the Main Thread
public class Test extends Thread
{
    public static void main(String[] args)
    {
        // getting reference to Main thread
        Thread t = Thread.currentThread();
        
        // getting name of Main thread
        System.out.println("Current thread: " + t.getName());
        
        // changing the name of Main thread
        t.setName("Geeks");
        System.out.println("After name change: " + t.getName());
        
        // getting priority of Main thread
        System.out.println("Main thread priority: "+ t.getPriority());
        
        // setting priority of Main thread to MAX(10)
        t.setPriority(MAX_PRIORITY);
        
        System.out.println("Main thread new priority: "+ t.getPriority());
        
        
        for (int i = 0; i < 5; i++)
        {
            System.out.println("Main thread");
        }
        
        // Main thread creating a child thread
        ChildThread ct = new ChildThread();
        
        // getting priority of child thread
        // which will be inherited from Main thread
        // as it is created by Main thread
        System.out.println("Child thread priority: "+ ct.getPriority());
        
        // setting priority of Main thread to MIN(1)
        ct.setPriority(MIN_PRIORITY);
        
        System.out.println("Child thread new priority: "+ ct.getPriority());
        
        // starting child thread
        ct.start();
    }
}
// Child Thread class
class ChildThread extends Thread
{
    @Override
    public void run()
    {
        for (int i = 0; i < 5; i++)
        {
            System.out.println("Child thread");
        }
    }
}

Output:

Current thread: main
After name change: Geeks
Main thread priority: 5
Main thread new priority: 10
Main thread
Main thread
Main thread
Main thread
Main thread
Child thread priority: 10
Child thread new priority: 1
Child thread
Child thread
Child thread
Child thread
Child thread

Relation between the main() method and main thread in Java

For each program, a Main thread is created by JVM(Java Virtual Machine). The “Main” thread first verifies the existence of the main() method, and then it initializes the class. Note that from JDK 6, main() method is mandatory in a standalone java application.

Deadlocking with use of Main Thread(only single thread)

We can create a deadlock by just using Main thread, i.e. by just using a single thread. The following java program demonstrate this.

// Java program to demonstrate deadlock
// using Main thread
public class Test
{
    public static void main(String[] args)
    {
        try
        {
            
            System.out.println("Entering into Deadlock");
            
            Thread.currentThread().join();
            
            // the following statement will never execute
            System.out.println("This statement will never execute");
            
        }
        
        catch (InterruptedException e)
        {
            e.printStackTrace();
        }
    }
}

Output:

Entering into Deadlock

Explanation :
The statement “Thread.currentThread().join()”, will tell Main thread to wait for this thread(i.e. wait for itself) to die. Thus Main thread wait for itself to die, which is nothing but a deadlock.

 

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

 

 

File Permissions in Java

Java provides a number of method calls to check and change the permission of a file, such as a read-only file can be changed to have permissions to write. File permissions are required to be changed when the user want to restrict the operations permissible on a file. For example, a file permission can be changed from write to read-only because the user no longer want to edit the file.

Checking the current file permissions

A file can be in any combination of following permissible permissions:

  • Executable: Tests whether the application can execute the file denoted by this abstract path name.
    Syntax:

    public boolean canExecute()
    Returns: true if and only if the abstract path name
    exists and the application is allowed to execute the file
  • Readable: Tests whether the application can read the file denoted by this abstract path name.
    Syntax:

    public boolean canRead()
    Returns: true if and only if the file specified by this
    abstract path name exists and can be read by the application; false otherwise
  • Writable: Tests whether the application can modify the file denoted by this abstract path name.
    Syntax:

    public boolean canWrite()
    Returns: true if and only if the file system actually
    contains a file denoted by this abstract path name and
    the application is allowed to write to the file; false otherwise.

For example, a file can be readable and writable but not executable. Here’s Java program to get the current permissions associated with a file.

// Java program to check the current file permissions.
import java.io.*;

public class Test
{
    public static void main(String[] args)
    {
        // creating a file instance
        File file = new File("C:\\Users\\Mayank\\Desktop\\1.txt");

        // check if the file exists
        boolean exists = file.exists();
        if(exists == true)
        {
            // printing the permissions associated with the file
            System.out.println("Executable: " + file.canExecute());
            System.out.println("Readable: " + file.canRead());
            System.out.println("Writable: "+ file.canWrite());
        }
        else
        {
            System.out.println("File not found.");
        }
    }
}

Output

Executable: true
Readable: true
Writable: true

Changing file permissions

A file can have any combinations of the following permissions:

  • Executable
  • Readable
  • Writable

Here are methods to change the permissions associated with a file:

  • setExecutableA convenience method to set the owner’s execute permission for this abstract path name.
    public boolean setExecutable(boolean executable)
    Description: 
    Parameters: executable - If true, sets the access
    permission to allow execute operations;
    if false to disallow execute operations
    Returns: true if and only if the operation succeeded.

    The operation will fail if the user does not have permission to change the access permissions of this abstract path name. If executable is false and the underlying file system does not implement an execute permission, then the operation will fail.

  • setReadable: A convenience method to set the owner’s read permission for this abstract path name.
    public boolean setReadable(boolean readable)
    Parameters: readable - If true, sets the access permission to
    allow read operations; if false to disallow read operations
    Returns: true if and only if the operation succeeded.

    The operation will fail if the user does not have permission to change the access permissions of this abstract path name. If readable is false and the underlying file system does not implement a read permission, then the operation will fail.

  • setWritable : A convenience method to set the owner’s write permission for this abstract path name.
    public boolean setWritable(boolean writable)
    Parameters: writable - If true, sets the access permission
    to allow write operations; if false to disallow write operations
    Returns: true if and only if the operation succeeded.

    The operation will fail if the user does not have permission to change the access permissions of this abstract path name.

// Java program to change the file permissions
import java.io.*;

public class Test
{
    public static void main(String[] args)
    {
        // creating a new file instance
        File file = new File("C:\\Users\\Mayank\\Desktop\\1.txt");

        // check if file exists
        boolean exists = file.exists();
        if(exists == true)
        {
            // changing the file permissions
            file.setExecutable(true);
            file.setReadable(true);
            file.setWritable(false);
            System.out.println("File permissions changed.");

            // printing the permissions associated with the file currently
            System.out.println("Executable: " + file.canExecute());
            System.out.println("Readable: " + file.canRead());
            System.out.println("Writable: "+ file.canWrite());

        }
        else
        {
            System.out.println("File not found.");
        }
    }
}

Output

File permissions changed.
Executable: true
Readable: true
Writable: false

 

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

 

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Abstract Classes in Java

In C++, if a class has at least one pure virtual function, then the class becomes abstract. Unlike C++, in Java, a separate keyword abstract is used to make a class abstract.

// An example abstract class in Java
abstract class Shape {
    int color;

    // An abstract function (like a pure virtual function in C++)
    abstract void draw();
}

Following are some important observations about abstract classes in Java.

1) Like C++, in Java, an instance of an abstract class cannot be created, we can have references of abstract class type though.

abstract class Base {
    abstract void fun();
}
class Derived extends Base {
    void fun() { System.out.println("Derived fun() called"); }
}
class Main {
    public static void main(String args[]) {

        // Uncommenting the following line will cause compiler error as the
        // line tries to create an instance of abstract class.
        // Base b = new Base();

        // We can have references of Base type.
        Base b = new Derived();
        b.fun();
    }
}

Output:

Derived fun() called

2) Like C++, an abstract class can contain constructors in Java. And a constructor of abstract class is called when an instance of a inherited class is created. For example, the following is a valid Java program.

// An abstract class with constructor
abstract class Base {
    Base() { System.out.println("Base Constructor Called"); }
    abstract void fun();
}
class Derived extends Base {
    Derived() { System.out.println("Derived Constructor Called"); }
    void fun() { System.out.println("Derived fun() called"); }
}
class Main {
    public static void main(String args[]) {
       Derived d = new Derived();
    }
}

Output:

Base Constructor Called
Derived Constructor Called

3) In Java, we can have an abstract class without any abstract method. This allows us to create classes that cannot be instantiated, but can only be inherited.

// An abstract class without any abstract method
abstract class Base {
    void fun() { System.out.println("Base fun() called"); }
}

class Derived extends Base { }

class Main {
    public static void main(String args[]) {
        Derived d = new Derived();
        d.fun();
    }
}

Output:

Base fun() called

4) Abstract classes can also have final methods (methods that cannot be overridden). For example, the following program compiles and runs fine.

// An abstract class with a final method
abstract class Base {
    final void fun() { System.out.println("Derived fun() called"); }
}

class Derived extends Base {}

class Main {
    public static void main(String args[]) {
       Base b = new Derived();
       b.fun();
    }
}

Output:

Derived fun() called

 

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

 

 

Perfect Numbers

Given a number and check if a number is perfect or not. A number is said to be perfect if sum of all its factors excluding the number itself is equal to the number.

Input:
First line consists of T test cases. Then T test cases follow .Each test case consists of a number N.

Output:
Output in a single line 1 if a number is a perfect number else print 0.

Constraints:
1<=T<=300
1<=N<=10000

Example:
Input:
2
6
21
Output:
1
0

**For More Examples Use Expected Output**

 

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Merge Two Sorted Arrays

You have to merge the two sorted arrays into one sorted array (in non-increasing order)

Input:

First line contains an integer T, denoting the number of test cases.
First line of each test case contains two space separated integers X and Y, denoting the size of the two sorted arrays.
Second line of each test case contains X space separated integers, denoting the first sorted array P.
Third line of each test case contains Y space separated integers, denoting the second array Q.
Output:

For each test case, print (X + Y) space separated integer representing the merged array.
Constraints:

1 <= T <= 100
1 <= X, Y <= 5*104
0 <= Pi, Qi <= 109
Example:

INPUT:

1
4 5
7 5 3 1
9 8 6 2 0

OUTPUT:

9 8 7 6 5 3 2 1 0

**For More Examples Use Expected Output**

 

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Minimum number of deletions and insertions.

Given two strings ‘str1’ and ‘str2’ of size m and n respectively. The task is to remove/delete and insert minimum number of characters from/in str1 so as to transform it into str2. It could be possible that the same character needs to be removed/deleted from one point of str1 and inserted to some another point.

Input:

The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains integers N and M denoting the length of the strings str1 and str2. Both the strings consist of only small letter alphabets.

The second line of each test case contains the strings str1 and str2.
Output:

Print the total no of insertions and deletions to be done to convert str1 to str2. Output the answer in a new line.
Constraints:

1<= T <=100

1<= N, M <=1000
Example:

Input:

1

4 3

heap pea

Output:

3

**For More Examples Use Expected Output**

 

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Connect Nodes at Same Level (Function Program)

Write a function to connect all the adjacent nodes at the same level in a binary tree. Structure of the given Binary Tree node is like following.

struct Node{

int data;

Node* left;

Node* right;

Node* nextRight;

}
Initially, all the nextRight pointers point to garbage values. Your function should set these pointers to point next right for each node.

Example:

Input Tree
       10
      / \
     3   5
    / \   \
   4   1   2


Output Tree
       10--->NULL
      / \
     3-->5-->NULL
    / \   \
   4-->1-->2-->NULL

 

Input:

The task is to complete the method which takes one argument, root of Binary Tree. There are multiple test cases. For each test case, this method will be called individually.

Output:
The function should update nextRight pointers of all nodes.

Constraints:
1 <=T<= 30
1 <=Number of nodes<= 100
1 <=Data of a node<= 1000

Example:
Input:

2
2
3 1 L 3 2 R
4
10 20 L 10 30 R 20 40 L 20 60 R

Output:
3 1 2
1 3 2
10 20 30 40 60
40 20 60 10 30

There are two test casess.  First case represents a tree with 3 nodes and 2 edges where root is 3, left child of 3 is 1 and right child of 3 is 2.   Second test case represents a tree with 4 edges and 5 nodes.

The output contains level order and inorder traversals of the modified tree.  Level order traversal is done using nextRight pointers.

 

Note:The Input/Ouput format and Example given are used for system’s internal purpose, and should be used by a user forExpected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.
 

**For More Examples Use Expected Output**

 

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

 

Begin Web Development with a Head Start

If you’re a budding engineer in the trade of IT or someone else with a fresh interest in website development and design, then this post is for you.

For over a decade, web development has been the most favourite subject for geeks all over the world and it’s not new. But the everyday growth and emerging techniques has made it even a more wondrous subject to learn and experiment on. In this article, I’ll write everything you need to know and everything you will require to pursue your journey in web development conveniently, more productively and with more fun!

Who can develop websites and web applications?

If you understand the basic logics of programming (loops, classes, objects, functions etc.), you can easily construct a web application as huge as Google Chrome. Nothing Fancy.

If you like spending your time with a code editor rather than doing other mediocre chores, then yes, you can be the next Zuckerburg.

Coding during web development is relatively easy than that in software designing but it still requires logic and a focused mind-set.

Who cannot develop websites and web applications?

If the only motivation behind all this work is academics and a decent résumé then you might face ‘technical’ problems as developing on web domains requires a lot of smart-work and dedication. If you don’t plan through, you might end up in nowhere with your interest and efforts completely ruined.

Why Development?

The trade of IT and Computer Science (CSE) is basically categorized into three sub-domains; Software engineering, Networking and website development. However former two are also very interesting and fruitful as web development, students are consistently made to believe that those are more important and significant than WebDev.

I can’t stress this point enough, Web Development and Designing is third wheel in computer technologies and it can’t be under-estimated.

I’ve personally seen people wandering in software engineering for jobs and careers regardless of their non-interests in field and after failing that, commencing website development.

Web Development is the future. Have a look around and you’ll agree.

Myths of Web Development

  • WebDev is limited to creating websites.
  • WebDev cannot get you ‘high-paid’ jobs.
  • WebDev is easy.

No Dear! Web Development is not limited to websites, you can create browsers, plugins, games, e-commerce and SOFTWARES too. The development scope is too vast, describing it would take more than one article. WebDev can get you jobs in high-reputed companies like Facebook, Microsoft, Google etc. or you could always work as a high-profiled freelancer. Although beginning career might disappoint you, but as you keep growing, so does your pay cheque.

Web Development, although fun, requires hard work especially during PHP/ASP.net phase. You have to work in a specific order if you want to become a good web developer.

Basic Roadmap

Step 1 – HTML5

Though easy it seems, HTML5 is certainly not the old HTML as we know it. HTML5 is the extended functional form of HTML4 with many more features than the former version. With HTML5, you can not only prepare basic webpage structure easily, but can store variables on page itself, create games on it, don’t need to rely on flash anymore to run your videos and animation and with a nice 4 months in-depth study, can even create full functioning blog, without even touching server side languages like PHP.

Time Required: 4 months*

Avoid Head-start and HTML5 for dummies book as they are not much practical on subject.

Step 2 – CSS

Who adds colours to rainbows? CSS surely does.

With the application of CSS, you can define your web in a colourful and smooth way. Like HTML, CSS has grew into CSS3, with which, you can also add transitions to pages, scrolls and even mouse hovers. You can even make your site elegant or flashy by using just few lines of CSS3.

Time Required: 1 Month practice with HTML5*

Step 3 – HTML5 & CSS

Now as you learned HTML5 and CSS3 so far, designing pages won’t look much hard to you. You can either design your own pages or templates or can work into responsive layouts that can adapt any device’s screen.

You can practice as much as you want, but 60-hours* are just enough to practice using HTML5 and CSS3 together. If you’re a brilliant student, you can also look up bootstrap3 for responsive layout, before moving to step 4.

Step 4 – HTML5 & JavaScript

Now, after learning how your site should look, you can actually make those buttons useful in some tasks. JavaScript, the best work-around coding language for webpages is versatile, flexible and platform independent. I prefer it over any other web-programming language (client-side). With javascripts, real development starts. You create variables, assign them some values, and pass them as arguments in some function to finally get returned some values or actions (e.g. page loading, redirecting). JavaScript is easy to learn but hard to master, so I recommend moving to next step as soon as you learn the working of functions and variables. JavaScript has many children like node.js and it requires a lot of reading and practice to actually make some use in creating complex web applications. (See Macros).

Step 5 –  HTML5 & PHP

So far, it’s all about developing a website from front-end. How it looks and how should it react, but real work takes place behind the curtains. PHP is a server-side language, and it handles all the real work and completely relies on your internet connection (unless you’re working on local host which I don’t recommend for projects).

  • First Half of these learning procedure is working on front-end
  • Second Half requires more back-coding

Time required: 4 Months (500 hours at least)*

Step 6 – All above + MySQL

Easiest to work, hardest to maintain. Designing on database can be a real pain if you’re not organized and well-planned.

The reason I recommend PHP over any other server-scripting languages is that PHP is great for beginners and if your basic old-school C++ concepts are clear, PHP becomes much easier than you anticipate.

MySQL, with the combination of PHP on Apache server (better than IIS) provides a perfect frame to build webpages and if you want to practice on localhost, try WAMP server.

Practice on local host, implement on remote host.

Books Recommended : Head-first MySQL by O’reilly

 Step 7- Python, Ruby on rails, Perl etc.

If you followed the steps above in sequence as mentioned, you probably know already the working of a social networking website and how notifications and personal messages (chats) works.

You can create an e-commerce easily, without even moving further to next step. But what if you want to create websites like FlipKart, Amazon, Microsoft, Google or Facebook?

Those are more complicated than just HTML5, PHP and MySQL.

There are other server and client side coding languages to help you do wonders you always wished. Python is one of the most practical, efficient and profitable coding language that is being used today and the best thing about learning python is it’s very easy.

Although, Python is independent of PHP but I still recommend learning PHP first as it will prepare your mind-set and you will learn python more quickly.

I worked on PHP for six years, and learned python in 12 hours.

There are other coding languages and framework on which you can work on like Ruby on rails. But Python should be your first preference.

 Step 8 – Mix-it-up

The final step. Mix-it-up.

Use HTML5 with python, load python codes in HTML5 browser, implement PHP codes on python or simply write a python application to work up some JavaScript.

Practice-Practice-Practice!!!

It would take some time before you begin to create your own big project that someday might replace major web-technology brands, but every hike starts with a small step.

Thanks for reading, if you have any more pointers, suggestions, arguments or appreciations, post a comment!

*All these are my time estimates and may vary individual to individual.

P.S – WebDev and WebDav. WebDav means Web Distributed authoring and versioning- a completely different thing.

 

 

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

 

Smallest element in an array that is repeated exactly ‘k’ times.

Given an array of size n, the goal is to find out the smallest number that is repeated exactly ‘k’ times where k > 0?
Assume that array has only positive integers and 1 <= arr[i] < 1000 for each i = 0 to n -1.

Examples:

Input : arr[] = {2 2 1 3 1}
        k = 2
Output: 1
Explanation:
Here in array,
2 is repeated 2 times
1 is repeated 2 times
3 is repeated 1 time
Hence 2 and 1 both are repeated 'k' times
i.e 2 and min(2, 1) is 1

Input : arr[] = {3 5 3 2}
        k = 1
Output : 2
Explanation:
Both 2 and 5 are repeating 1 time but
min(5, 2) is 2

Simple Approach: A simple approach is to use two nested loops.The outer loop picks an element one by one starting from the leftmost element. The inner loop checks if the same element is present on right side of it. If present increase the count and make the number negative which we got at the right side to prevent it from counting again.

// C++ program to find smallest number
// in array that is repeated exactly
// 'k' times.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
int findDuplicate(int arr[], int n, int k)
{
    // Since arr[] has numbers in range from
    // 1 to MAX
    int res = MAX + 1;
    for (int i = 0; i < n; i++) {
        if (arr[i] > 0) {
            // set count to 1 as number is present
            // once
            int count = 1;
            for (int j = i + 1; j < n; j++)
                if (arr[i] == arr[j])
                    count += 1;
            // If frequency of number is equal to 'k'
            if (count == k)
                res = min(res, arr[i]);
        }
    }
    return res;
}
// Driver code
int main()
{
    int arr[] = { 2, 2, 1, 3, 1 };
    int k = 2;
    int n = sizeof(arr) / (sizeof(arr[0]));
    cout << findDuplicate(arr, n, k);
    return 0;
}

Output:

1

Time Complexity : O(n2)
Auxiliary Space : O(1)
This solution doesn’t require array elements to be in limited range.

Better Solution : Sort the input array and find the first element with exactly k count of appearances.

 

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org