An array has elements(1,2,2,1,1). I have to find the number of distinct elements in the sub array should be equal to the number of distinct elements in the given array i.e the number of distinct elements in the array is 2 (1 and 2).
All the possible subarrays are [1,2] , [1,3] , [1,4] , [1,5] , [2,4] , [2,5] , [3,4] , [3,5]
Distinct means no of distinct elements it 2 {1,2,2} has 2 distinct elements. In this question 1,4 doesn't mean we are including 1st element and 4th element it means our sub array starts from 1 and end at 4 thus sub array is [1,2,2,1] which has 2 distinct element and it satisfies as the whole array has 2 distinct element.
The problem of the que is that i get test case of array size of 2 lacs and i have to get the output in 1 second and each time i get time limit exceed occurs.
After seeing the answer i have to use buffer reader(instead of scanner {due to performance issue}) and hashmap.
Firstly, i used scanner and buffer reader and both gave output in 2 min 17sec(for 2 lac input). So why there is need to use buffer reader(using scanner reduced the length of the code).
Secondly,i tested both the code on the site and both the code gave output within 1 second whereas in my local machine it took 2 min 17 sec. i didn't understand why there is so much difference.
Third,what is the meaning of this code: final int mod = (int)1e9+7; (though i have seen many times when using large number)
Fourth,What is the use of the below code used with the buffered reader.
I am novice in java so pls give simple answer and sorry for the long post
class InputReader
{
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream)
{
this.stream = stream;
}
public int read()
{
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars)
{
curChar = 0;
try
{
numChars = stream.read(buf);
} catch (IOException e)
{
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int readInt()
{
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-')
{
sgn = -1;
c = read();
}
int res = 0;
do
{
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public String readString()
{
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do
{
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public double readDouble() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
double res = 0;
while (!isSpaceChar(c) && c != '.') {
if (c == 'e' || c == 'E')
return res * Math.pow(10, readInt());
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
}
if (c == '.') {
c = read();
double m = 1;
while (!isSpaceChar(c)) {
if (c == 'e' || c == 'E')
return res * Math.pow(10, readInt());
if (c < '0' || c > '9')
throw new InputMismatchException();
m /= 10;
res += (c - '0') * m;
c = read();
}
}
return res * sgn;
}
public long readLong() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c)
{
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public String next()
{
return readString();
}
public interface SpaceCharFilter
{
public boolean isSpaceChar(int ch);
}
}
class OutputWriter
{
private PrintWriter writer;
public OutputWriter(OutputStream outputStream)
{
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer)
{
this.writer = new PrintWriter(writer);
}
public void print(Object... objects)
{
for (int i = 0; i < objects.length; i++)
{
if (i != 0)
writer.print(' ');
writer.print(objects[i]);
}
}
public void printLine(Object... objects)
{
print(objects);
writer.println();
}
public void close()
{
writer.close();
}
public void flush()
{
writer.flush();
}
}
Answer to your fourth Query : The code is faster than using normal Scanner class. Hence you can use it in coding competetions. I made the used the following code on a ~55 MB text file "test.txt".
package so;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Scanner;
public class UseIR {
public static void main(String[] args) throws IOException {
//checked using the class provided 'InputReader'
InputReader ob=new InputReader(new FileInputStream(new File("src\\so\\test.txt")));
long str=0;
StringBuilder sb=new StringBuilder();
long curTime=System.currentTimeMillis();
while((str=ob.read())!=-1){
sb.append(((char)str));
}
System.out.println("done "+(System.currentTimeMillis()-curTime));
//checked using the Scanner class
curTime=System.currentTimeMillis();
Scanner s=new Scanner(new File("src\\so\\test.txt"));
sb=new StringBuilder();
while(s.hasNext()){
sb.append(s.next());
}
System.out.println("done "+(System.currentTimeMillis()-curTime));
}
}
With the following Output:
done 447
done 2061
Hope it helps :)