[Easy-Medium] Algo challenge #3

[Raul]

Propun o noua problema care necesita o logica buna.

 

Se da un array de numere intregi si pozitive. Singura alterare permisa a elementelor din array este incrementarea acestora, strict cu valoarea 1. Toate numerele din array trebuie sa devina pare, intr-un final, cu un numar minim de incrementari, dar respectand regula urmatoare: atunci cand se face o incrementare pe pozitia i din array, in mod obligatoriu se face incrementare fie pe pozitia i-1, fie pe pozitia i+1. Se cere returnarea numarului minim de incrementari, astfel incat, in final, toate numerele din array sa fie pare. In cazul in care input-ul nu este valid, deci nu se poate ajunge la un rezultat corect, se va returna -1.

 

Constrangeri:

Se considera N a fi numarul de elemente din array, iar 2 <= N <= 1000

1 <= V[i] <= 10, iar 0 <= i <= N-1

 

Exemplu #1: Se da V = [4,5,6,7]. Se face incrementare, la primul pas, pe i = 2 si respectiv i = 3, deci va rezulta array-ul V = [4,5,7,8]. Acum, la pasul urmator, se va face incrementare pe i = 1 si respectiv i = 2, deci va rezulta array-ul V = [4,6,8,8]. In final, se intoarce numarul de incrementari facute, mai exact 4.

Exemplu #2: Se da V = [2,3,4,5,6]. Se face incrementare, la primul pas, pe i = 1 si respectiv i = 2, deci va rezulta array-ul V = [2,4,5,5,6]. Acum, la pasul urmator, se va face incrementare pe i = 2 si respectiv i = 3, deci va rezulta array-ul V = [2,4,6,6,6]. In final, se intoarce numarul de incrementari facute, mai exact 4.

Exemplu #3: Se da V = [1,2]. Oricum s-ar face incrementare, una dintre valori va fi mereu para, iar cealalta impara. Prin urmare, nu se poate ajunge la un rezultat corect, deci se intoarce -1.

 

Limbajul care va fi folosit este la alegere libera. Sunt acceptate toate solutiile, indiferent de complexitatea timp, dar trebuie incercat sa se rezolve in maxim O(N). O solutie personala va fi pusa ulterior.

Spor!

Edited December 20, 2018 by Raul

[Raul]

Esti destul de aproape, dar, din pacate, solutia nu este complet valida. O sa pun aici niste testcase-uri pe care da fail.

Link: https://pastebin.com/iZwL3Gjn

[Raul]

Just now, Gecko said:

Am postat v2 in acelasi post pentru a nu ocupa spatiu prea mult.

Testat, este in regula, a trecut toate testcase-urile, kudos!

Sunt binevenite si alte propuneri, in continuare!

Edited December 17, 2018 by Raul

[theandruala]

public class MuieGO2 {

	public static void main(String[] args) {

		int[] arrayfrumos = { 2, 3, 4, 5, 6 };
		int[] test2 = { 3, 8, 4, 6, 1, 9, 8, 8, 6, 7, 5, 2, 1, 5, 8, 6, 1, 3, 3, 9, 3, 7, 8, 5, 5, 4, 7, 2, 9, 8, 7, 7,
				4, 4, 7, 1, 5, 3, 10, 7, 10, 10, 9, 1, 9, 10, 1, 10, 2, 7, 2, 10, 2, 7, 8, 10, 3, 8, 1, 3, 4, 1, 6, 1,
				5, 3, 10, 7, 6, 10, 6, 6, 1, 6, 3, 9, 6, 8, 4, 9, 5, 3, 7, 7, 3, 5, 4, 2, 7, 5, 6, 4, 3, 10, 4, 5, 2, 4,
				7, 5, 6, 10, 3, 4, 8, 4, 10, 7, 8, 9, 1, 10, 2, 6, 4, 10, 1, 2, 6, 3, 6, 4, 9, 6, 6, 2, 8, 8, 5, 9, 7,
				4, 2, 10, 10, 6, 4, 7, 2, 8, 4, 5, 6, 1, 1, 7, 3, 5, 2, 7, 10, 1, 6, 2, 2, 9, 3, 1, 10, 1, 2, 5, 5, 5,
				4, 9, 9, 7, 9, 2, 6, 4, 2, 10, 9, 2, 8, 8, 10, 9, 1, 7, 3, 3, 7, 4, 9, 3, 3, 3, 1, 6, 5, 2, 7, 9, 4, 1,
				4, 1, 10, 7, 8, 6, 4, 6, 5, 6, 1, 1, 7, 6, 1, 8, 5, 3, 3, 4, 5, 7, 10, 3, 10, 9, 8, 10, 9, 2, 3, 9, 6,
				3, 3, 10, 5, 3, 3, 1, 10, 8, 6, 5, 8, 5, 8, 7, 5, 5, 9, 6, 1, 9, 5, 2, 8, 8, 1, 8, 7, 1, 7, 3, 4, 3, 7,
				7, 5, 4, 7, 10, 7, 3, 3, 9, 2, 4, 2, 7, 1, 6, 6, 3, 2, 1, 5, 4, 6, 7, 8, 8, 9, 10, 5, 1, 1, 10, 3, 7, 3,
				5, 2, 6, 4, 7, 4, 6, 8, 10, 10, 4, 3, 10, 7, 1, 5, 1, 6, 1, 5, 8, 6, 10, 2, 4, 9, 10, 2, 1, 8, 9, 1, 6,
				4, 4, 9, 5, 9, 3, 2, 3, 4, 8, 9, 5, 6, 10, 3, 1, 3, 4, 7, 4, 8, 9, 9, 8, 10, 4, 3, 6, 7, 1, 9, 6, 8, 4,
				7, 6, 8, 9, 2, 4, 6, 8, 1, 8, 7, 9, 5, 7, 9, 10, 4, 2, 5, 3, 2, 2, 8, 2, 10, 10, 9, 1, 10, 10, 7, 6, 9,
				2, 1, 4, 3, 4, 5, 9, 8, 6, 9, 4, 3, 10, 6, 8, 10, 2, 4, 2, 9, 5, 7, 4, 7, 6, 10, 3, 5, 8, 2, 5, 3, 8, 8,
				2, 10, 4, 3, 6, 9, 3, 5, 10, 10, 8, 6, 4, 6, 1, 10, 9, 3, 4, 7, 3, 7, 10, 7, 4, 2, 5, 3, 9, 2, 6, 6, 4,
				4, 2, 4, 3, 2, 10, 1, 6, 7, 5, 2, 8, 2, 9, 4, 3, 4, 9, 3, 4, 9, 6, 8, 5, 5, 8, 3, 6, 8, 7, 6, 9, 9, 3,
				1, 8, 9, 5, 10, 5, 4, 9, 9, 3, 6, 8, 10, 1, 9, 6, 7, 5, 3, 10, 1, 2, 9, 4, 4, 4, 6, 3, 6, 9, 2, 5, 9, 8,
				6, 8, 6, 7, 5, 6, 3, 10, 1, 2, 2, 5, 6, 9, 5, 6, 5, 10, 5, 2, 7, 1, 2, 10, 7, 7, 7, 1, 1, 7, 6, 4, 5, 7,
				4, 10, 6, 4, 5, 9, 3, 5, 10, 7, 1, 10, 1, 9, 6, 3, 5, 6, 5, 5, 6, 2, 9, 4, 8, 8, 10, 1, 3, 6, 2, 2, 2,
				2, 9, 3, 7, 6, 6, 1, 1, 2, 10, 5, 9, 2, 7, 4, 8, 1, 4, 9, 6, 8, 7, 6, 7, 9, 8, 4, 2, 1, 3, 10, 7, 2, 7,
				8, 4, 1, 10, 6, 9, 7, 4, 7, 8, 10, 3, 4, 6, 10, 7, 10, 7, 2, 6, 1, 9, 6, 9, 4, 6, 2, 4, 9, 6, 5, 8, 4,
				10, 4, 5, 5, 10, 4, 5, 8, 7, 2, 8, 2, 1, 6, 9, 3, 8, 3, 4, 5, 5, 3, 7, 10, 5, 7, 9, 2, 6, 7, 9, 3, 5, 8,
				4, 4, 2, 6, 6, 1, 9, 2, 9, 5, 7, 4, 4, 7, 4, 2, 8, 1, 6, 6, 9, 2, 2, 4, 7, 5, 3, 2, 8, 5, 6, 10, 1, 1,
				3, 5, 5, 1, 5, 4, 4, 3, 10, 5, 1, 10, 1, 7, 2, 8, 9, 3, 6, 6, 2, 7, 3, 6, 6, 4, 7, 9, 10, 2, 3, 3, 10,
				9, 7, 5, 7, 5, 5, 10, 5, 4, 10, 2, 5, 6, 6, 7, 7, 3, 2, 9, 2, 9, 1, 1, 2, 6, 8, 1, 2, 9, 10, 8, 2, 7,
				10, 9, 2, 1, 5, 4, 8, 2, 4, 9, 1, 1, 7, 4, 10, 3, 1, 9, 3, 7, 7, 8, 8, 5, 1, 4, 1, 1, 10, 1, 7, 9, 5, 1,
				8, 7, 9, 10, 1, 7, 2, 10, 5, 4, 1, 7, 8, 5, 8, 9, 9, 6, 1, 8, 7, 3, 9, 10, 6, 5, 9, 2, 7, 3, 5, 1, 1, 5,
				6, 10, 9, 5, 10, 4, 4, 5, 9, 6, 4, 3, 2, 2, 2, 6, 6, 5, 1, 5, 2, 1, 3, 6, 1, 5, 8, 9, 9, 5, 3, 10, 6, 8,
				2, 4, 3, 8, 4, 10, 3, 10, 5, 1, 10, 1, 9, 8, 7, 1, 6, 6, 4, 2, 1, 3, 6, 8, 7, 7, 10, 5, 8, 7, 7, 4, 8,
				8, 1, 4, 5, 3, 10, 1, 7, 1, 7, 6, 10, 4, 7, 8, 5, 3, 2, 3, 5, 9, 9, 9, 10, 9, 9, 9, 8, 1, 2, 6, 9, 9, 7,
				8, 1, 5, 9, 8, 6, 9, 2, 6 };
		int[] test3 = { 5, 6, 4, 10, 6, 2, 4, 10, 4, 2, 2, 10, 5, 10, 10, 10, 10, 6, 2, 4, 4, 2, 6, 2, 2, 10, 10, 8, 2,
				2, 6, 6, 6, 10, 10, 4, 2, 2, 6, 2, 8, 10, 10, 10, 6, 10, 2, 2, 10, 2, 4, 10, 10, 2, 8, 10, 6, 2, 2, 8,
				6, 2, 8, 4, 7, 6, 2, 4, 2, 8, 6, 8, 9, 6, 4, 6, 8, 10, 4, 6, 8, 10, 6, 10, 6, 10, 2, 4, 9, 4, 6, 2, 4,
				2, 8, 4, 8, 6, 6, 9, 4, 7, 6, 6, 4, 5, 6, 10, 10, 5, 8, 2, 10, 2, 10, 10, 8, 10, 8, 8, 8, 10, 8, 6, 8,
				6, 2, 4, 2, 6, 4, 8, 6, 10, 8, 3, 10, 4, 10, 8, 5, 5, 6, 4, 4, 10, 2, 10, 2, 8, 6, 4, 6, 8, 4, 2, 2, 4,
				4, 8, 8, 1, 4, 10, 2, 10, 4, 10, 4, 10, 4, 2, 10, 8, 5, 2, 2, 2, 2, 6, 4, 10, 2, 4, 5, 2, 4, 10, 10, 6,
				2, 2, 7, 8, 4, 6, 6, 6, 6, 8, 10, 6, 4, 2, 6, 10, 2, 2, 10, 2, 4, 8, 6, 4, 4, 8, 4, 4, 4, 6, 6, 8, 8, 4,
				10, 4, 10, 2, 8, 8, 8, 4, 10, 4, 10, 4, 6, 8, 10, 2, 10, 8, 10, 10, 6, 6, 10, 8, 8, 8, 6, 2, 10, 8, 10,
				4, 2, 10, 6, 4, 2, 4, 6, 8, 10, 8, 6, 6, 8, 10, 2, 6, 4, 10, 4, 6, 6, 2, 6, 6, 2, 4, 4, 4, 8, 6, 6, 1,
				10, 10, 8, 4, 2, 6, 6, 10, 2, 2, 2, 6, 8, 2, 6, 8, 2, 8, 8, 8, 10, 4, 8, 8, 10, 6, 2, 4, 6, 6, 1, 6, 6,
				2, 2, 2, 8, 2, 2, 8, 4, 8, 4, 4, 8, 10, 6, 10, 4, 4, 10, 6, 10, 10, 8, 6, 6, 4, 6, 2, 4, 10, 8, 6, 8,
				10, 2, 6, 4, 2, 4, 2, 8, 5, 10, 10, 10, 6, 2, 6, 4, 6, 4, 4, 2, 6, 2, 10, 8, 8, 4, 4, 9, 4, 2, 6, 4, 10,
				4, 6, 8, 4, 8, 6, 2, 6, 8, 6, 2, 10, 5, 6, 6, 2, 2, 4, 8, 4, 10, 8, 2, 4, 10, 8, 2, 8, 6, 10, 8, 8, 8,
				10, 6, 8, 3, 10, 8, 8, 6, 6, 4, 8, 6, 4, 8, 6, 10, 4, 10, 6, 1, 6, 8, 10, 2, 10, 2, 10, 8, 4, 8, 6, 6,
				6, 6, 2, 6, 6, 4, 2, 10, 4, 10, 6, 4, 8, 4, 4, 8, 2, 8, 8, 9, 8, 3, 2, 3, 2, 6, 6, 2, 8, 2, 2, 10, 2, 4,
				2, 6, 5, 2, 6, 2, 2, 2, 2, 2, 8, 10, 2, 2, 10, 10, 6, 6, 10, 8, 4, 8, 4, 6, 8, 4, 4, 4, 6, 6, 8, 1, 6,
				9, 6, 2, 6, 8, 2, 8, 8, 2, 6, 6, 8, 8, 6, 6, 10, 8, 2, 10, 10, 6, 6, 10, 4, 6, 6, 10, 6, 6, 2, 10, 4, 8,
				8, 2, 2, 8, 1, 4, 6, 8, 10, 4, 2, 8, 2, 2, 10, 10, 10, 6, 10, 4, 6, 2, 4, 2, 8, 10, 8, 10, 7, 4, 2, 4,
				8, 2, 10, 2, 4, 8, 10, 8, 10, 8, 2, 6, 4, 2, 8, 2, 4, 4, 8, 10, 8, 6, 8, 2, 4, 10, 4, 8, 8, 8, 6, 2, 6,
				2, 2, 1, 2, 10, 2, 4, 8, 6, 10, 8, 8, 2, 6, 4, 2, 10, 4, 2, 4, 4, 2, 8, 4, 10, 8, 7, 10, 10, 8, 2, 8, 2,
				6, 8, 4, 2, 4, 8, 10, 10, 2, 8, 6, 4, 8, 8, 10, 4, 8, 3, 8, 2, 6, 4, 4, 8, 8, 10, 6, 2, 10, 2, 6, 3, 10,
				2, 2, 10, 8, 2, 2, 10, 4, 6, 4, 4, 6, 4, 8, 10, 2, 3, 2, 6, 6, 6, 10, 10, 8, 2, 6, 4, 6, 4, 2, 10, 3, 2,
				6, 4, 7, 4, 4, 8, 2, 8, 2, 4, 4, 2, 6, 4, 6, 6, 8, 10, 10, 4, 8, 8, 6, 10, 6, 6, 8, 10, 6, 10, 4, 4, 2,
				6, 4, 10, 8, 8, 8, 4, 10, 4, 2, 10, 6, 4, 10, 2, 6, 8, 10, 2, 2, 4, 4, 6, 6, 6, 6, 8, 2, 4, 8, 4, 4, 10,
				4, 4, 2, 10, 8, 6, 2, 4, 2, 8, 8, 4, 6, 4, 4, 10, 2, 10, 6, 10, 4, 4, 2, 4, 10, 2, 8, 6, 8, 6, 10, 2, 8,
				2, 4, 2, 10, 2, 6, 8, 6, 6, 6, 6, 2, 6, 2, 4, 10, 2, 8, 4, 4, 6, 10, 10, 2, 8, 2, 2, 6, 8, 4, 4, 2, 4,
				10, 2, 4, 6, 8, 4, 10, 10, 10, 8, 3, 8, 4, 8, 10, 10, 4, 8, 3, 8, 6, 1, 6, 8, 4, 2, 10, 4, 2, 10, 6, 6,
				8, 6, 8, 10, 2, 10, 8, 2, 10, 8, 10, 8, 2, 8, 8, 2, 2, 4, 10, 6, 2, 8, 10, 6, 4, 4, 8, 8, 2, 2, 6, 2, 2,
				4, 4, 8, 10, 2, 2, 4, 8, 8, 4, 10, 5, 10, 6, 2, 10, 10, 8, 4, 10, 8, 10, 4, 2, 2, 7, 7, 4, 2, 10, 4, 8,
				2, 8, 10, 2, 2, 4, 8, 2, 2, 10, 10, 6, 10, 8, 8, 2, 6, 4, 2, 7, 6, 2, 10, 6, 10, 8, 8, 10, 2, 10, 10, 2,
				2, 4, 10, 10, 4, 6, 8, 8, 8, 6, 6, 4, 10, 4, 3, 4, 6, 6, 2, 5, 8, 8, 2, 5 };

		System.out.println("Am facut " + functieFrumoasa(test3) + " incrementari.");
	}

	static int functieFrumoasa(int[] arrayfrumos) {
		int incrementari = 0;
		if (arrayfrumos.length == 2) {

			if (arrayfrumos[0] % 2 != arrayfrumos[1] % 2) {
				System.out.println("Tzeapa n-ai mai loat tzeapa?");
				return -1;
			} else {
				return 1;
			}
		}

		for (int i = 0; i < arrayfrumos.length - 1; i++) {
			if (true) {//casamoaraheitarii
				if (arrayfrumos[i] % 2 == 1) {
					incrementari += 2;
					arrayfrumos[i] += 1;
					arrayfrumos[i + 1] += 1;
				}
			}
		}

		System.out.println();
		for (int i = 0; i < arrayfrumos.length; i++) {
			if (arrayfrumos[i] % 2 == 1) {
				return -1;
			}
		}
		return incrementari;
	}

}

 

Edited December 17, 2018 by theandruala

[Raul]

Testat, este in regula, a trecut toate testcase-urile, kudos!

 

Solutia mea (Golang) este urmatoarea:

func solve(B []int32) int {
    counter, sum, ok := 0, 0, true
    for _, v := range B {
        sum += v
        if sum % 2 == 1 {
            ok = false
            counter += 2
            continue
        }
        ok = true
    }
    if !ok {
        return -1
    }
    return counter
}

* Problema este adaptata de la ceva asemanator gasit pe HackerRank

Edited December 17, 2018 by Raul