Header Ad

HackerEarth Partial Digit Sequence problem solution

In this HackerEarth Partial Digit Sequence problem solution You are given an array A of length N. The partial digit subsequence of an array A is a subsequence of integers in which each consecutive integers have at least 1 digit in common. You are required to find the length of the longest partial digit subsequence from the given array.


HackerEarth Partial Digit Sequence problem solution


HackerEarth Partial Digit Sequence problem solution.

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.InputStream;

public class Solution{
public static void main(String[] args) {
new Thread(null, new Runnable() {
public void run() {
new Solution().solve();
}
}, "1", 1 << 26).start();
}

void solve() {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
ScanReader in = new ScanReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
PARTIAL_DIGIT_SEQUENCE solver = new PARTIAL_DIGIT_SEQUENCE();
solver.solve(1, in, out);
out.close();
}

static class PARTIAL_DIGIT_SEQUENCE {
public void solve(int testNumber, ScanReader in, PrintWriter out) {
int n = in.scanInt();
int[] ans = new int[10];
for (int i = 0; i < n; i++) {
long temp = in.scanLong();
boolean[] digits = new boolean[10];
while (temp > 0) {
digits[(int) (temp % 10)] = true;
temp /= 10;
}
int max = 0;
for (int j = 0; j < 10; j++) if (digits[j]) max = Math.max(ans[j], max);
for (int j = 0; j < 10; j++) if (digits[j]) ans[j] = max + 1;
}
int answer = 0;
for (int i = 0; i < 10; i++) answer = Math.max(answer, ans[i]);
out.println(answer);


}

}

static class ScanReader {
private byte[] buf = new byte[4 * 1024];
private int index;
private BufferedInputStream in;
private int total;

public ScanReader(InputStream inputStream) {
in = new BufferedInputStream(inputStream);
}

private int scan() {
if (index >= total) {
index = 0;
try {
total = in.read(buf);
} catch (Exception e) {
e.printStackTrace();
}
if (total <= 0) return -1;
}
return buf[index++];
}

public int scanInt() {
int integer = 0;
int n = scan();
while (isWhiteSpace(n)) n = scan();
int neg = 1;
if (n == '-') {
neg = -1;
n = scan();
}
while (!isWhiteSpace(n)) {
if (n >= '0' && n <= '9') {
integer *= 10;
integer += n - '0';
n = scan();
}
}
return neg * integer;
}

private boolean isWhiteSpace(int n) {
if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
else return false;
}

public long scanLong() {
long integer = 0;
int n = scan();
while (isWhiteSpace(n)) n = scan();
int neg = 1;
if (n == '-') {
neg = -1;
n = scan();
}
while (!isWhiteSpace(n)) {
if (n >= '0' && n <= '9') {
integer *= 10;
integer += n - '0';
n = scan();
}
}
return neg * integer;
}

}
}


Second solution

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define si(x) scanf("%d",&x)
#define pi(x) printf("%d\n",x)
#define s(x) scanf("%lld",&x)
#define p(x) printf("%lld\n",x)
#define sc(x) scanf("%s",x)
#define pc(x) printf("%s",x)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define inf 1e18
#define prec(x) fixed<<setprecision(15)<<x
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define mem(x,y) memset(x,y,sizeof(x))
#define PQG priority_queue< int,std::vector<int>,std::greater<int> >
#define PQL priority_queue< int,std::vector<int>,std::less<int> >
#define PQPL priority_queue<pii ,vectosr< pii >, less< pii > >
#define PQPG priority_queue<pii ,vector< pii >, greater< pii > >
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)

using namespace std;

int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
#endif
int n; cin>>n;
assert(n>=1 && n<=100000);
string s[n];
for(int i=0;i<n;i++) {
cin>>s[i];
ll x=0;
for(char c:s[i]) {
x=x*10+(ll)(c-'0');
}
assert(x>=1 && x<=inf);
}
int cnt[10];
memset(cnt,0,sizeof(cnt));
for(int i=0;i<n;i++) {
int sz=s[i].size();
set<int>ss;
for(int j=0;j<sz;j++) {
ss.insert(s[i][j]-'0');
}
int val=0;
for(int x:ss) val=max(val,cnt[x]);
for(int x:ss) cnt[x]=val+1;
}
int ans=0;
for(int i=0;i<10;i++) {
ans=max(ans,cnt[i]);
}
cout<<ans<<endl;

return 0;
}

Post a Comment

0 Comments