Header Ad

HackerEarth Minimum indexes problem solution

In this HackerEarth Minimum indexes problem solution You are given an array A of Q integers and Q queries. In each query, you are given an integer i (1 <= i <= N).

Your task is to find the minimum index greater than i (1 <= i <= N) such that:
  1. Sum of digits of Ai is greater than the sum of digits of Aj
  2. Ai < Aj
If there is no answer, then print -1.


HackerEarth Minimum indexes problem solution


HackerEarth Minimum indexes problem solution.

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define endl "\n"
#define ll long long
#define sz(s) (int)(s.size())
#define INF 0x3f3f3f3f3f3f3f3fLL
#define all(v) v.begin(),v.end()
#define watch(x) cout<<(#x)<<" = "<<x<<endl
const int dr[] { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] { 0, 1, 1, 1, 0, -1, -1, -1 };
#if __cplusplus >= 201402L
template<typename T>
vector<T> create(size_t n) {
return vector<T>(n);
}
template<typename T, typename ... Args>
auto create(size_t n, Args ... args) {
return vector<decltype(create<T>(args...))>(n, create<T>(args...));
}
#endif
void run() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.in", "r", stdin);
#else
#endif
}

struct segment_tree {
#define LEFT (idx<<1)
#define RIGHT (idx<<1|1)
#define MID ((start+end)>>1)
int n;
vector<int> tree;
segment_tree(int n = 0) :
n(n), tree(n << 2) {
}
void update(int idx, int start, int end, int pos, int val) {
if (start == end) {
tree[idx] = val;
return;
}
if (pos <= MID)
update(LEFT, start, MID, pos, val);
else
update(RIGHT, MID + 1, end, pos, val);
tree[idx] = max(tree[LEFT], tree[RIGHT]);
}
int query(int idx, int start, int end, int l, int r, int val) {
if (r < start || end < l || tree[idx] <= val)
return n;
if (start == end)
return start;
int rt = query(LEFT, start, MID, l, r, val);
if (rt < n)
return rt;
return query(RIGHT, MID + 1, end, l, r, val);
}
void update(int pos, int val) {
update(1, 0, n - 1, pos, val);
}
int query(int l, int r, int val) {
return query(1, 0, n - 1, l, r, val);
}
} seg[9 * 9 + 1];

int sumDigits(int a) {
if (a == 0)
return 0;
return a % 10 + sumDigits(a / 10);
}
int main() {
run();
int n, q;
cin >> n >> q;
for (int i = 0; i <= 81; i++)
seg[i] = segment_tree(n);
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
seg[sumDigits(v[i])].update(i, v[i]);
}
while (q--) {
int i;
cin >> i;
i--;
int sum = sumDigits(v[i]);
int ans = n;
for (int j = 0; j < sum; j++)
ans = min(ans, seg[j].query(i + 1, n - 1, v[i]));
if (ans == n)
ans = -2;
cout << ans + 1 << endl;
}
}

Second solution

[n, q] = map(int, input().split())
a = list(map(int, input().split()))
while q > 0:
q -= 1
i = int(input()) - 1
ans = -2
for j in range(i + 1, n):
if a[i] < a[j] and sum(map(int, str(a[i]))) > sum(map(int, str(a[j]))):
ans = j
break
print(ans + 1)

Post a Comment

0 Comments