Mad Scientist

Introduction

A mad scientist performed a series of experiments, each having n phases. During each phase, a measurement was taken, resulting in a positive integer of magnitude at most k. The scientist knew that an individual experiment was designed in a way such that its measurements were monotonically increasing, that is, each measurement would be at least as big as all that precede it. For example, here is a sequence of measurements for one such experiment with n=13 and k=6:

1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 6

It was also the case that n was to be larger than k, and so there were typically many repeated values in the measurement sequence. Being mad, the scientist chose a somewhat unusual way to record the data. Rather than record each of n measurements, the scientist recorded a sequence P of k values defined as follows. For 1 ≤ j ≤ k, P(j) denoted the number of phases having a measurement of j or less. For example, the original measurements from the above experiment were recorded as the P-sequence:

2, 7, 7, 8, 12, 13

as there were two measurements less than or equal to 1, seven measurements less than or equal to 2, seven measurement less than or equal to 3, and so on. Unfortunately, the scientist eventually went insane, leaving behind a notebook of these P-sequences for a series of experiments. Your job is to write a program that recovers the original measurements for the experiments.

Solutions

Idea

Each successive integer in the input corresponds to the number of measurements at that value, where the value is defined to be the index in the input list. The general idea is to keep a counter that corresponds to the current measurement value. Then, depending on how many measurements are at that counter value, add that many number of measurements to a list of all measurements. At this point, all you have to do is print out the contents of the list holding your measurements.

Runtime

n, where n is the number of phases of the experiment (the largest number given in the input list)

Code

Solution - Java

import java.util.ArrayList;
import java.util.Scanner;

/**
 * Created by alex on 9/17/15.
 */
public class MadScientist {

    public static void main (String args[]){
        Scanner in = new Scanner(System.in);
        while(true){
            int k = in.nextInt();
            if(k == 0){
                break;
            }
            ArrayList<Integer> experiment = new ArrayList<Integer>();
            int counter = 0;
            for(int i = 0; i<k; i++){
                counter++;
                int numberOfExperiments = in.nextInt();
                for(int j=experiment.size(); j<numberOfExperiments; j++) {
                    experiment.add(counter);
                }
            }

            //output
            for(int m = 0; m<experiment.size()-1; m++){
                System.out.print(experiment.get(m) + " ");
            }
            System.out.print(experiment.get(experiment.size()-1));
            System.out.println();
        }
    }
}