In this HackerRank What’s Next? problem solution we have given an array A, find integer array C and print its length on a new line then print the elements of array C as a single line of space-separated integers.
Problem solution in Python.
import sys
T = int(input().strip())
for _ in range(T):
binary_A = []
n = int(input().strip())
A = list( map(int, input().strip().split()) )
if n > 1:
if n % 2 == 0:
if n >= 4:
if A[n - 3] == 1:
if A[n - 2] != 1:
A[n - 2] -= 1
A[n - 4] += 1
A[n - 3] += A[n - 1]
del A[n - 1]
else:
A[n - 4] += 1
A[n - 3] += A[n - 1]
del A[n - 2]
del A[n - 2]
else:
A[n - 3] -= 1
A[n - 2] -= 1
for _ in range(2):
A.insert(n - 2, 1)
A[n - 1] += A[n + 1]
del A[n + 1]
else:
if A[n - 2] == 1:
A[n - 1] += 1
else:
A = [1, A[n - 1] + 1, A[n - 2] - 1]
else:
if A[n - 2] == 1:
if A[n - 1] != 1:
A[n - 1] -= 1
A[n - 3] += 1
else:
A[n - 3] += 1
del A[n - 1]
else:
A[n - 2] -= 1
A[n - 1] -= 1
for _ in range(2):
A.insert(n - 1, 1)
else:
A[0] -= 1
for _ in range(2):
A.insert(0, 1)
if A[-1] == 0:
del A[-1]
print (len(A))
print (' '.join(str(x) for x in A))
Problem solution in Java.
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for (int i = 0; i < n; i++) {
int len = scanner.nextInt();
BigInteger[] a = new BigInteger[len];
for (int j = 0; j < len; j++) {
a[j] = new BigInteger(scanner.next());
}
BigInteger[] result = new NextNumber().nextNumber(a);
System.out.println(result.length);
for (int j = 0; j < result.length; j++) {
System.out.print(result[j] + " ");
}
System.out.println();
}
}
}
class NextNumber {
public BigInteger[] nextNumber(BigInteger[] binary) {
ArrayList<BigInteger> result = new ArrayList<>();
BigInteger[] dataToProcess;
if (binary.length % 2 == 0) {
for (int i = 0; i < binary.length - 2; i++) {
result.add(binary[i]);
}
dataToProcess = new BigInteger[2];
dataToProcess[0] = binary[binary.length - 1];
dataToProcess[1] = binary[binary.length - 2];
} else {
for (int i = 0; i < binary.length - 1; i++) {
result.add(binary[i]);
}
dataToProcess = new BigInteger[1];
dataToProcess[0] = binary[binary.length - 1];
}
BigInteger[] secondPart = process(dataToProcess);
if (result.size() > 0) {
result.set(result.size() - 1, result.get(result.size() - 1).subtract(new BigInteger("1")));
}
for (int i = 0; i < secondPart.length; i++) {
result.add(secondPart[i]);
}
result = removeZeros(result);
BigInteger[] ret = new BigInteger[result.size()];
for (int i = 0; i < result.size(); i++) {
ret[i] = result.get(i);
}
return ret;
}
private ArrayList<BigInteger> removeZeros(ArrayList<BigInteger> result) {
while (result.stream().anyMatch(x -> x.equals(new BigInteger("0")))) {
int itemToRemove = -1;
for (int i = 0; i < result.size(); i++) {
if (result.get(i).equals(new BigInteger("0"))) {
itemToRemove = i;
}
}
if (itemToRemove >= 0) {
result.set(itemToRemove - 1, result.get(itemToRemove - 1).add(result.get(itemToRemove + 1)));
result.remove(itemToRemove);
result.remove(itemToRemove);
}
}
return result;
}
public BigInteger[] process(BigInteger[] data) {
BigInteger onesCount;
BigInteger zerosCount;
if (data.length == 2) {
onesCount = data[1];
zerosCount = data[0];
} else {
onesCount = data[0];
zerosCount = new BigInteger("0");
}
ArrayList<BigInteger> resultData = new ArrayList<>();
resultData.add(new BigInteger("1"));
onesCount = onesCount.subtract(new BigInteger("1"));
if (zerosCount.compareTo(new BigInteger("0")) > 0) {
resultData.add(zerosCount.add(new BigInteger("1")));
} else {
resultData.add(new BigInteger("1"));
}
if (onesCount.compareTo(new BigInteger("0")) > 0) {
resultData.add(onesCount);
}
BigInteger[] result = new BigInteger[resultData.size()];
for (int i = 0; i < resultData.size(); i++) {
result[i] = resultData.get(i);
}
return result;
}
}
Problem solution in C++.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
using namespace std;
typedef unsigned long long ul_t;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int t;
cin >> t;
while(t--){
int n;
cin >> n;
std::vector<ul_t> v(n);
for(auto &a : v) cin >> a;
ostringstream outOSS;
if(n%2==1){
if(n==1){
outOSS << "1 1 ";
if(v[0]>1) outOSS << v[0]-1 << " ";
}
else{
for (int i = 0; i < n-3; ++i) outOSS << v[i] << " ";
const ul_t x = v[n-3];
const ul_t y = v[n-2];
const ul_t z = v[n-1];
if(y==1) outOSS << x+1 << " 1 ";
else outOSS << x << " " << y-1 << " 1 1 ";
if(z>1) outOSS << z-1 << " ";
}
}
else if(n%2==0){
if(n==2){
outOSS << "1 ";
if(v[0]>1) outOSS << v[1]+1 << " " << v[0]-1 << " ";
else outOSS << v[1]+1 << " ";
}
else{
for (int i = 0; i < n-4; ++i) outOSS << v[i] << " ";
const ul_t x = v[n-4];
const ul_t y = v[n-3];
const ul_t z = v[n-2];
const ul_t q = v[n-1];
if(y==1) outOSS << x+1 << " ";
else outOSS << x << " " << y-1 << " 1 ";
if(z>1) outOSS << q+1 << " " << z-1 << " ";
else outOSS << q+1 << " ";
}
}
string s = outOSS.str();
cout << count(s.begin(), s.end(),' ') << endl;
cout << outOSS.str() << endl;
}
return 0;
}
Problem solution in C.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
unsigned long long A[n+2];
for(int i=0;i<n;i++){
scanf("%llu",&A[i]);
}
if(n%2==1){
if(n==1){
if(A[0]>1){
n+=2;
A[2]=A[0]-1; A[1]=1; A[0]=1;
}
else{
n++;
A[1]=1;
}
}
else if(A[n-2]==1){
if(A[n-1]>1){
A[n-1]-=1; A[n-3]+=1;
}
else{
A[n-3]+=1;
n--;
}
}
else{
if(A[n-1]>1){
n+=2;
A[n-1]=A[n-3]-1; A[n-2]=1; A[n-3]=1; A[n-4]--;
}
else{
n+=1;
A[n-3]--; A[n-2]=1; A[n-1]=1;
}
}
}
else{
if(n==2){
if(A[n-2]>1){
//110 -> 1001
n+=1;
A[2]=A[0]-1; A[1]+=1; A[0]=1;
}
else{
A[1]++;
}
}
else if(A[n-2]==1){
if(A[n-3]>1){
A[n-1]++; A[n-3]--;
}
else{
A[n-4]++;
A[n-3]=A[n-1]+1;
n-=2;
}
}
else{
if(A[n-3]>1){
n++;
A[n-1]=A[n-3]-1;
A[n-2]++;
A[n-3]=1;
A[n-4]--;
}
else{
A[n-4]++;
A[n-3]=A[n-1]+1;
A[n-2]--;
n--;
}
}
}
printf("%dn",n);
for(int i=0;i<n;i++){
printf("%llu ",A[i]);
}
printf("n");
}
return 0;
}
