Algorithm


Problem Name: Data Structures - Kindergarten Adventures

Problem Link: https://www.hackerrank.com/challenges/kindergarten-adventures/problem?isFullScreen=true

In this HackerRank in Data Structures - Kindergarten Adventures solutions

Meera teaches a class of n students, and every day in her classroom is an adventure. Today is drawing day! The students are sitting around a round table, and they are numbered from 1 to n n the clockwise direction. This means that the students are numbered 1, 2,3 ,..., n - 1, n, and students 1 and n are sitting next to each other. After letting the students draw for a certain period of time, Meera starts collecting their work to ensure she has time to review all the drawings before the end of the day. However, some of her students aren't finished drawing! Each student i needs ti extra minutes to complete their drawing. Meera collects the drawings sequentially in the clockwise direction, starting with student ID x and it takes her exactly 1 minute to review each drawing. This means that student x gets 0 extra minutes to complete their drawing, student x + 1 gets 1 extra minute, student x +2 gets 2 extra minutes, and so on. Note that Meera will still spend 1 minute for each student even if the drawing isn't ready.

Given the values of t1,t2,...,tn help Meera choose the best possible x to start collecting drawings from, such that the number of students able to complete their drawings is maximal. Then print  on a new line. If there are multiple such IDs, select the smallest one.

Input Format

The first line contains a single positive integer, n denoting the number of students in the class.

The second line contains n space-separated integers describing the respective amounts of time that each student needs to finish their drawings (i.e., t1,t2,...,tn)

Constraints

  • 1 <= n <= 10**5
  • 0 <= ti <= n

Subtasks

  • 1 <= n <= 10**4 for 30% of the maximum score.

Output Format

Print an integer denoting the ID number,

, where Meera should start collecting the drawings such that a maximal number of students can complete their drawings. If there are multiple such IDs, select the smallest one.

Sample Input 1

Array: t
1
0
0
3
1 0 0

Sample Output 1

2

 

 

 

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
  int n;
  scanf("%d", &n);
  int * arr = malloc(sizeof(int) * n);
  memset(arr, 0, sizeof(int) * n);
  for (int i = 0; i  <  n; i++) {
    int t;
    scanf("%d", &t);
    if (0  <  t && t < n) {
      arr[(i + 1) % n]++;
      arr[(i - (t - 1) + n) % n]--;
    }
  }
  int runningSum = arr[0];
  int maxRunningSum = runningSum;
  int index = 0;
  for (int i = 1; i  <  n; i++) {
    runningSum += arr[i];
    if (runningSum > maxRunningSum) {
      maxRunningSum = runningSum;
      index = i;
    }
  }
  free(arr);
  printf("%d\n", index + 1);

  return 0;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i = 0; i  <  N; i++) {
        cin >> A[i];
    }

    int start = 0;

    vector<int> D(N+1, 0);
    for(int i = 0; i  <  N; i++) {
        if(A[i] <= i) {
            start++;
            D[i-A[i]]--;
            D[i]++;
        } else {
            D[i-A[i]+N]--;
            D[i]++;
        }
    }

    int best = start;
    int bi = 0;
    int cur = start;
    for(int i = 0; i  <  N; i++> {
        if(cur > best) {
            best = cur;
            bi = i;
        }
        cur += D[i];
    }

    cout << (bi+1) << endl;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - Java Programming


import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        List < Integer> start = new ArrayList();
        List end = new ArrayList();
        for(int i = 0; i  <  n; i++){
            int drawTime = in.nextInt();
            if(drawTime != 0 && drawTime != n){
                int s = i + 1;
                int e = i + n - drawTime;
                if(s == n){
                    start.add(0);
                    end.add(e - n);
                }else if (e >= n){
                    start.add(s);
                    end.add(n - 1);
                    start.add(0);
                    end.add(e - n);
                }else{
                    start.add(s);
                    end.add(e);
                }
            }
        }
        Collections.sort(start);
        Collections.sort(end);
        int maxIndex = 0;
        int maxValue = 0;
        int currValue = 0;
        int sp = 0;
        int ep = 0;
        while(sp < start.size()){
            int sv = start.get(sp);
            int ev = end.get(ep);
            if(sv  < = ev>{
                currValue++;
                if(currValue > maxValue){
                    maxValue = currValue;
                    maxIndex = sv;
                }
                sp++;
            }else {
                currValue--;
                ep++;
            }
        }
        System.out.println(maxIndex+1);
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Javascript Programming

Code - Javascript Programming


'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the solve function below.
 */

function solve(t) { 
  let n = t.length;
  let diffArr = [];
  for (let i = 0; i  <  t.length; i++) {
    if (t[i] >= n || t[i] === 0) continue;
    // add one to next index
    let addToIndex = (i + 1) % n;
    diffArr[addToIndex] = ~~diffArr[addToIndex] + 1;
    // subtract one from ending index
    let endIndex = i - t[i] + 1;
    if (endIndex  <  0) endIndex += n;
    diffArr[endIndex] = ~~diffArr[endIndex] - 1;
  }

  let maxIndex = 0;
  let currentMax = Number.MIN_SAFE_INTEGER;
  let sum = 0;
  for (let i = 0; i  <  diffArr.length; i++) {
    sum += ~~diffArr[i];
    if (sum > currentMax) {
      maxIndex = i;
      currentMax = sum;
    }
  }
  return maxIndex + 1;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const tCount = parseInt(readLine(), 10);

    const t = readLine().split(' ').map(tTemp => parseInt(tTemp, 10));

    let id = solve(t);

    ws.write(id + "\n");

    ws.end();
}
Copy The Code & Try With Live Editor

#5 Code Example with Python Programming

Code - Python Programming


n = int(input().strip())
a = list(map(int, input().strip().split()))
b = [0 for i in range(n)]
for i in range(n):
    v = a[i]
    if 0 == v or v >= n - 1:
        continue
    i1 = i - v + 1
    i2 = i + 1
    if i1 < 0:
        i1 += n
    if i2 >= n:
        i2 -= n;
    b[i1] -= 1
    b[i2] += 1
result, mv, tmp = 0, 0, 0
for i in range(n):
    tmp += b[i]
    if 0 == i or tmp > mv:
        result = i
        mv = tmp
#print(b)
print(result + 1)
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Contacts solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Mr. X and His Shots solution in Hackerrank - Hacerrank solution C, C++, java,js, Python