You are a given pyramid of integer numbers. Your task is to print a growing sequence of integers, starting from the top of the pyramid.
For example, we are given the following pyramid:
2
5 8
4 9 10
The first number from the top is 2. Going bottom, on the second row, the closest number larger than 2 is 5. On the third row, the closest number larger than 5 is 9. The resulting sequence is {2, 5, 9}.
If a row does not contain a number larger than the previous one, we go to the next row and search for a number greater than the previous number + 1.
For example:
6
5 3 //(6 + 1 = 7)
4 9 7
The first number is 6. On the second row we have no number greater than 6, so we go to the next row, where we look for the nearest number larger than 7 (6 + 1 = 7), which is 9. The resulting sequence is {6, 9}.
Input
The input will be read from the console.
- On the first line, you will get the number of lines N.
- On the next N you will get the rows of the pyramid. The numbers in each row are separated by one or more spaces. There will be a different number of spaces at the beginning of each line.
The input data will always be valid and in the format described. There is no need to check it explicitly.
Output
Print on the console all numbers of the sequence separated by a comma and a space.
Constraints
- The first row will contain only 1 number.
- The rows of the pyramid will be in the range [2 … 1000].
- The numbers in the pyramid will be integers in the range [-2147483648 … 2147483647].
- Time limit: 0.3 sec. Memory limit: 16 MB.
Examples
Here is my solution - you can carefully read the comments - as I explain there everything! 🙂
package com.somesite.java;
import java.util.ArrayList;
import java.util.Scanner;
public class Pyramid {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine());//READ HOW MANY ROWS WILL BE IN THE PYRAMID
int firstNum = Integer.parseInt(scanner.nextLine().trim());//READ THE FIRST NUMBER FROM THE PYRAMID + TRIM: REMOVE THE WHITE SPACES
ArrayList<Integer> outputNums = new ArrayList<>();//KEEPING THE FINAL NUMBERS: THE OUTPUT IN AN ArrayList; THE ArrayList WILL ADD THE COMAS (,) AUTOMATICALLY BETWEEN THE NUMBERS
outputNums.add(firstNum);//THE firstNum WILL ALWAYS BE THE FIRST ONE TO BE SHOWN IN THE ArrayList; THE OTHER NUMBERS WILL BE ADDED ON LINE 41
for (int i = 1; i < n; i++) {//THE INITIAL i=1; BECAUSE WE ALREADY READ THE FIRST NUMBER: firstNum - SO WE NEED TO TAKE THE SECOND (NEXT) ONE
String[] nums = scanner.nextLine().trim().split("\\s+");//WRITING THE NUMBERS FROM THE PYRAMID + PUT THEM INTO AN ARRAY OF STRINGS (AFTERWARDS THE NUMBERS WILL BE PARSED INTO INTEGERS)
int closestNumber = Integer.MAX_VALUE;
int smallestDifference = Integer.MAX_VALUE;//USING Integer.MAX_VALUE IN CASE THERE ARE NEGATIVE NUMBERS
boolean hasBigger = false;
for (int j = 0; j < nums.length; j++) {//WORKING WITH THE NUMBERS FROM THE STRING ARRAY nums
int currentNum = Integer.parseInt(nums[j]);//WORKING WITH THE CURRENT NUMBER FROM THE ARRAY
if (currentNum > firstNum) {//AVOID GETTING NEGATIVE currentNum
int currentDif = currentNum - firstNum;
if (currentDif < smallestDifference) {
closestNumber = currentNum;
smallestDifference = currentDif;
hasBigger = true;
}
}
}
if (!hasBigger) {
firstNum++;
} else {
outputNums.add(closestNumber);//ADDING THE NUMBERS IN THE ArrayList outputNums (THE FIRST NUMBER firstNum IS ALREADY THERE - SEE LINE 15)
firstNum = closestNumber;//THE firstNum BECOMES THE NEXT closestNumber - NOT THE INITIAL ONE: firstNum
}
}
System.out.print(outputNums.toString().replace("[", "").replace("]", ""));//PRINTING THE OUTPUT + REPLACING THE BRACKETS "[" AND "]"
}
}
