- Practice
- Algorithms
- Implementation
- Fair Rations
- Discussions

# Fair Rations

# Fair Rations

WatchandLearn + 21 comments In this problem the thing is if sum of all number is even ,then array can be even. if sum of all number is odd , then the answer is NO.

My java solution is here;

public class Solution {

`public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int B[] = new int[N]; int sum = 0; for(int B_i=0; B_i < N; B_i++){ B[B_i] = in.nextInt(); sum+=B[B_i]; } int count = 0; if(sum % 2 == 1){ System.out.println("NO"); } else{ for(int i = 0; i<N; i++){ if(B[i] % 2 != 0){ B[i] = B[i] + 1; B[i+1] = B[i+1] + 1; count+=2; } } System.out.println(count); } }`

}

RaviShekhar93 + 2 comments Nice thinking!! Also B[i]+1 is unncessesary.. And boundaries check needed.. But really elegant logic..

Shadow3797 + 0 comments Run the loop till N-1,works for all test cases and no boundary checks needed

Lychkin + 0 comments [deleted]cgajardo + 2 comments How did you came up with this?

"In this problem the thing is if sum of all number is even ,then array can be even. if sum of all number is odd , then the answer is NO."

I've been struggling about how to determinate if the array is solvable or not.

Thanks for sharing!

christosg8 + 1 comment If the total sum is odd, then by always adding 2 loaves of bread, the sum will still be odd, since odd + 2 == odd.

In order for every person to have an even number of loaves of bread the total sum should be even, since even + even + ... + even == even, after the N additions of 2 loaves.

Hope this helps!

intechworx + 0 comments Thanks, that helps

devilizer + 0 comments see dude whenever u make a addition in array u make it in even no. i.e 2, so u need the whole array sum to be even to make each element even.

[deleted] + 0 comments Smart insight!

daminiaglawe30 + 0 comments nice and elegant solution

MrAsimov + 3 comments consider the case 1 1 1. in this case sum of all number is odd but answer is YES . please explain.

cyberpirate92 + 1 comment for 1 1 1 the answer is NO

chris236 + 0 comments [deleted]

Shubham_Sankalp7 + 0 comments it would be NO as number of odd number in the 1 1 1 is 3 i.e Odd.

chris236 + 0 comments I thought the same as you because I misread the problem. I thought you had to give to the person behind

*and*before:[1 1 1] ^ [2 2 2]

But you have to give to the person behind

*or*before:[1 1 1] ^ [1 2 2]

ryanfehr18 + 2 comments This is not actually optimal, because you are still performing it in O(2n). If you instead nest your bread distribution iteration within your array intialization you can reach O(n) time and in that case there is no benefit to knowing the sum, because by the time you gain knowledge of the sum of the array you are already at the last element and can determine it without the sum. Therefore in the same space using a integer as a carry variable instead of a sum variable you are able to achieve this in the same space complexity proposed here, but with half the time required.

Best of luck!

conkosidowski + 6 comments I saw your gist you posted. Looks simple, but I came up with something I think is simpler.

int N = in.nextInt(); int sum = 0; int count = 0; for(int i=0; i < N; i++){ sum += in.nextInt(); if (sum % 2 == 1) { count += 2; } } System.out.println(sum % 2 == 0 ? count : "NO");

I don't like posting solutions but I like this one and the OP already posted a solution ;)

ryanfehr18 + 0 comments I totally dig this solution, I had wrote my solution to this problem a long time ago and completely overlooked the O(n) solution using O(1) space. Nice job

RishabhKejariwal + 0 comments nice work!

kirtigarg167 + 0 comments the logic is out of the box great job!!

mike_buttery + 0 comments O(n) in python by counting the number of flips between pairs of odd numbers

used modulo as boolean

`even%2`

is equivalent to`False`

and`odd%2`

is`True`

total = 0 a = None flips = 0 for i in range(len(arr)): if arr[i]%2 and a == None: total += 1 a = i elif arr[i]%2: total += 1 flips += i - a a = None return 'NO' if total%2 else flips * 2

Vardhan + 0 comments What a logic you have given!! How do you come up with such a simple and optimized Solution!

alexander_shiro1 + 1 comment In order to understand why the algo written by Conor Kosidowski is indeed correct, I added the formal analysis of the algo, that uses the loop invariant technique (following the CLRS book) to prove that the algo is indeed correct.

Loop invariant statement: both (a) and (b) below are true.

a) If "sum" is even, then "count" yields the correct number of loaves to distribute among [ 0, next(i) ) ; true otherwise.

b) If the "sum" is odd, then "count" shows the correct number of loaves to distribute into the line [ 0, next(i) ], assuming B[next(i)] is odd; and true otherwise.

Conventions: [A,B) denotes sequence of integers from A to B, excluding B.

Checking the Initialization, Maintenance and Termination requirements:

Initialization (checked just before first iteration):

`We need to check tha the loop invariant is true at this time. Indeed: we have next(i) = 0, hence [0,i) = [0,0) = [], - the line is empty. The sum is even, and count= 0 reflects correct number of loaves to distribute.`

Maintenance (checked just before each iteration):

`Let us check loop the invariant statements 1. Suppose "sum" is even. We know count = previous(count) in this case. We need to prove that the count yields correct number of loaves to distibute in [0,next("i")). 1.1) If "element" is even, then we know, the previous("sum") is even; Suppose we distribute previous("count") loaves in the line [0,i), so the requirements are satisfied for [0,i); we know we can do it by maintenance assumption; Since element is even, adding this element to line does not break the requirements, so we conclude the requirements are satisfied for [0,next("i")). The assertion is proven. 1.2) If element is odd, then we know the previous("sum") is odd, and by maintenance assumption, we know that the previous("count") (which is equal to the current value of count) yields the correct value of loaves to distribute in [0,next(previous("i"))] = [0,i] = [0,next(i)), assuming B[i] is odd which is indeed the case. Hence previous("i") which is equal to current "count", yields correct number of loaves to distibute in [0,next("i")). The assertion is proven. 2. Suppose "sum" is odd We know count = previous(count)+2 in this case Need to show: "count" shows the correct number of loaves to distribute into the line [ 0, next(i) ], assuming B[next(i)] is odd; 2.1. If "element" is even, then we know, the previous("sum") is odd; By maintenance assumption previous(count) shows the correct number of loaves to distribute into the line [ 0, previous(next(i)) ) = [0,i), extended by one more participant holding an odd number of loaves. We need two more loaves if we extend with even numbered element=B[i] and then with odd numbered B[next(i)], hence we need previous(count)+2 = count. The assertion if proven. 2.2 If "element" is odd, then we know previous("sum") is even. By maintenance assumption, previous("count") is the correct number of loaves to distribute to [0,next(previous("i")) = [0,i). Extending with the present odd numbered element and yet another odd element will require two more loaves. The assertion is proven.`

Termination (checked prior to terminating iteration):

`We terminate when next(i) = n At this time, if sum is even, then by loop invariant, the count yield the correct # of loaves to distribute in [0,next(i)) = [0,n). If sum is odd, then we know loaves cannot be distributed, so the answer is "N0"`

amoghk + 0 comments Interesting analysis. Although I feel this still doesn't prove that the algorithm is optimal. It proves that following the algorithm, if a solution (a way to make all even) is possible, it will be achieved; But it doesn't prove that this will be the optimal number of loaves. Correct me if I'm wrong.

rebecca_asely + 1 comment hello rÃ½anfehr18 sir i have found more optimize solution complexity is O(1) here is the code

`import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class FairRotation { public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int B[] = new int[N];int sum=0,sum1=0; for(int B_i=0; B_i < N; B_i++){ B[B_i] = B[B_i]+in.nextInt(); if(B[B_i]%2==1&&B_i+1<N) {sum+=2; B[B_i+1]+=1; } if(B_i==N-1&&B[B_i]%2==1) { System.out.println("NO");break; } if(B_i==N-1&&B[B_i]%2==0) { System.out.println(sum);break; } } } }`

conkosidowski + 3 comments Just curious... how do you figure this is O(1)?

rebecca_asely + 0 comments because O(n) is a linear time where loop runs exactly n times ... but m not using any extra loop at all since the answer is displayed the moment it fin8shes giving input because time complexity starts after the input is given...

rebecca_asely + 0 comments any how i optimize the code posted by ryanfehr18

ryanfehr18 + 1 comment This is something that is debated a decent amount, but in my opinion reading input is included in time complexity(On HackerRank). It counts on HackerRank because reading from Stdin is counted as part of the test case runtime. If the input was pulled before runtime was tracked and then passed to our functions, I could be swayed.

conkosidowski + 0 comments I would have to agree with you. I think this is O(n). If it was O(1) you would read the input by itself and find the output without loop. Putting logic in the loop you use to read the input doesn't make your solution O(1); your logic not only

*can*, but*must*loop N times.

octaVian001 + 1 comment Good thimking...but loop will be upto (n-1),,and in the IF statement logic should be changed because if B[i]=1 then condition will not be satisfied but 1 is odd..... Don't need to sum the array,after distribution if (n-1)th value is odd then print NO.

ryanfehr18 + 0 comments

PhoenixD + 1 comment Your test to determine if the test case is solvable or not is great, it helped me when i was struggling with the solution, but I came up with a different way to get the required number of loaves needed.

#include <cmath> #include <cstdio> #include <vector> #include <math.h> #include <iostream> #include <algorithm> #define forn(i,n) for(int i = 0;i<n;i++) using namespace std; int main() { int n,c=0,ans=0,t=0,k;cin>>n; vector<int> a(n); forn(i,n){ cin>>a[i]; if(a[i]%2!=0){ c++; if(t==0){ k=i;t=1; } else{ ans += 2*(i-k); t=0; } } } if(c%2!=0){ cout<<"NO"; } else{ cout<<ans; } return 0; }

Logic I used was that loaves would be given only to the people in between (including them too) 2 people having odd numbers of loaves, I counted the distance between each pairs of such people.

P.S, I am a newbie, Hope I made a valuable contribution and successfully explained my logic

psatishkumar720 + 0 comments very nice logic.

jgl359 + 0 comments [deleted]jgl359 + 0 comments [deleted]achathukulam + 0 comments excellent logic

achathukulam + 0 comments B[i]+1 is unnecessary.........

pankaj_pundir369 + 0 comments nice thinking

bbuddhabhushan + 0 comments Great

aryankuntal + 0 comments 2,3,4,10,8,5,6 may you distribut loafs please.

edrouwendaal + 2 comments C#, should be equivalent:

static int fairRations(int[] B) { int c = 0; for (int i = 1; i < B.Length; i++) { if (B[i - 1] % 2 != 0) { B[i - 1]++; B[i]++; c += 2; } if (B[i - 1] % 2 != 0) return -1; } if (B[B.Length - 1] % 2 != 0) return -1;//edge return c; }

h2418855831 + 0 comments Well done! Thank you!

vighneshpp_1986 + 0 comments a slightly simpler approach

int totalBreads = 0;

`for(int i=0;i<B.Length-1;i++){ if(B[i]%2!=0){ B[i]+=1; B[i+1] +=1; totalBreads+=2; } } if(B[B.Length-1]%2!=0){ return -1; } return totalBreads;`

riuvshyn + 0 comments hello, your algo is nice! however I;ve noticed that there is one redundant operation

for(int i = 0; i<N; i++){ if(B[i] % 2 != 0){ B[i] = B[i] + 1; <===== you don't need to add +1 to current element since you will never comeback here. B[i+1] = B[i+1] + 1; count+=2; }

sarathy_v_krish1 + 0 comments C++ solution :

#include<iostream> #include<vector> using namespace std; int main() { int n, index=0, sum=0, x; cin >> n; vector<int> v; while(n--) { cin >> x; if (x%2) v.push_back(index); index++; } if (v.size()%2){ cout << "NO"; return 0;} for (int i=1;i<v.size();i+=2) sum+=v[i]-v[i-1]; cout << sum*2; }

yogeshmahawar93 + 0 comments In other words:: If #of odd values is odd answer is going to be "No". No need to take sum.

sataaa + 5 comments Hmmm.. I made a completely different algorithm than the proposed one on the Editorial.

First, I check if there is an odd number of odds, because the way I understood it, when you give an odd a loaf, you "push the odd forward"... So it needs to reach another odd number so that both become even.

When I realised that, all that was left, after checking there was an even number of odds (so every odd could be pushed into another one), was to get the distances between odd numbers and multiply them by 2, because on every "push" you give 2 loaves of bread.

It's a real simple algorithm and isn't a greedy one.

swojit + 0 comments [deleted]gcapell + 0 comments +1. Also, you can do this in one pass with O(1) space, just keeping track of "where was the last unmatched odd we saw?"

feng12 + 0 comments this is a clever move :)

codeharrier + 4 comments It's simpler than that.

Use a carry value initialized to 0. When you see carry+input is odd, you count 2 loaves and set the carry to 1. If carry+input is instead even, set carry to 0.

After all the input is read, if the carry value from the last input is 1, the problem is insoluble, so you output NO, otherwise output the number of loaves counted.

`int loaves = 0; int carry = 0; while ( N-- ) { int i; cin >> i; if ( (carry + i)%2 ) { loaves += 2; carry = 1; } else carry = 0; } if ( carry ) cout << "NO" << endl; else cout << loaves << endl;`

or simpler still:

`while ( N-- ) { int i; cin >> i; carry = (carry + i)%2; loaves += 2*carry; }`

codingvsme + 1 comment Could you please tell me how did you get to this idea??? I mean thought process can you share... Idea is very good!!!

te777 + 2 comments I'd like to know too. Great code! I'm guessing that since you propogate loves distributed through the array, that ensures an even number for each element is the result until you reach the end and if the difference is 1 there then it is not possible. Am I correct? My Python3 version:

n = int(input().strip()) b = [int(B_temp) for B_temp in input().strip().split(' ')] sum = 0 carry = False for x in b: carry = (carry + x) % 2 sum += carry * 2 if carry: print("NO") else: print (sum)

te777 + 0 comments [deleted]codeharrier + 1 comment It's basically just following the rules as written.

As you check, you find intervals that start with an odd value, have even values in between, and end in an odd value. The process is symmetrical, so for any unhandled interval it doesn't matter whether you start at the leftward odd number or the rightward one, and you will never have to reverse course. And it can only be unbalanced when there is an interval that doesn't get balanced when it reaches the end.

You disturb two values each time you have to give out any loaves. So if an odd number is followed by an even one, adding loaves makes an even number followed by an odd one, which shortens the interval. When the odd value slides far enough to be next to another odd one, adding loaves closes the interval and you just look for the next one.

If you reach the end without an open interval, you're done, but if you're still handing out carried loaves, the solution can't be found.

codingvsme + 1 comment Thanks alot for detailed explaination!!!

te777 + 0 comments Thanks!

jcarlson08 + 0 comments If we're going for minimal code, embrace the ternary!

cout << (carry ? "NO" : loaves) << endl;

Eros10 + 0 comments if there will be only 2 elements having one element odd other even then fair distribution can't possible.

runcy + 0 comments ming blowing!

anusha30_karri + 0 comments +1 Simple solution

jbitshine + 3 comments In this version (C++) we don't use a vector and we use the input on the fly. We also run only one for loop, the one required to get all the variables of the list. Please feedback if there is some way to improve the following code:

#include <string> #include <iostream> using namespace std; int main(){ int N, input, oddity = 0, count = 0; cin >> N; for(int j = 0; j < N; j++){ cin >> input; if(input % 2) { count++; oddity = count % 2? oddity - j : oddity + j; } } cout << (count % 2 ? "NO" : to_string(oddity * 2)); return 0; }

kjds1238 + 1 comment i don't really understand your approach to the problem... can you please explain ?

itsmedurgesh + 0 comments you only need the value of gap between indices of two odd numbers because 2*gap is minimum number of breads must be given to make that interval even. If number of odds is odd this can't be done.

prash_cr07 + 0 comments Really nice logic.

diego_amicabile + 0 comments Similar approach:

N = int(input().strip()) B = [int(B_temp) for B_temp in input().strip().split(' ')] idx = [i for i, x in enumerate(B) if x % 2 == 1 ] if len(idx) % 2 == 1: print("NO") else: print(sum([(idx[i+1]-idx[i])*2 for i in range(0,len(idx),2)]))

klinMlin + 1 comment I don't know if anyone else will run into the same problem, but the solution I found found was change the code to

int result = fairRations(B); if(result==-1) bufferedWriter.write("NO"); else bufferedWriter.write(String.valueOf(result));

If the out put is NO, return -1.

rudratcs500 + 0 comments I ran into the same problem....thanks for the help man...

ShadowFiend + 1 comment My logic is : The obvious part : If the sum is odd then its NO.

When the sum is even : There are going to be even number of odd numbers. We have to neutralise each odd numbers in pairs. So there is a hidden sequence :

When the odd numbers are next to each other(3,3) it takes 2 loaves to equalise it, when the odd numbers are 1 integer(3,2,3) apart it takes 4 loaves and when they are 2 integers(3,2,2,3) apart it takes 6 loaves to neutralise them. It is in an AP sequence 2, 4 , 6 , 8 ......

So I use a+ (n-1) * d to find the number of loaves needed to neutralise. Please do tell me if this is efficient or do suggest imporvements. Thanks !`def fairRations(B): sumOfLoaves = 0; currentOddNumber = -1 pairedOddNumber = -1 distanceBetweenTwoOdds = 0 totalLoavesNeeded = 0; for breadLoavesWithPerson in B: sumOfLoaves += breadLoavesWithPerson if(breadLoavesWithPerson % 2 == 1 and currentOddNumber == -1): currentOddNumber = breadLoavesWithPerson pairedOddNumber = -1 distanceBetweenTwoOdds = 0 elif(currentOddNumber != -1 and breadLoavesWithPerson % 2 == 1): pairedOddNumber = breadLoavesWithPerson currentOddNumber = -1 loavesNeededToEqualise = (2 + ((distanceBetweenTwoOdds + 1) - 1) * 2) totalLoavesNeeded += loavesNeededToEqualise else: distanceBetweenTwoOdds += 1 if(sumOfLoaves % 2 == 1): return "NO" else : return totalLoavesNeeded`

Live_It_Abhi + 0 comments [deleted]

coder_aky + 0 comments # 100 % working , Simple and easy :-)

In Python 3

n,c,a=int(input()),0,list(map(int,input().split())) for i in range(0,len(a)-1): if a[i]%2!=0 : c=c+2 a[i+1]=a[i+1]+1 print(c if a[-1]%2==0 else 'NO')

SerhiiK + 0 comments Did in Python

O(N) complecity (no extra "moves" on the begining)

EEEOEEEOEOEEEOEEE look at that like chain EEE OEEEO E OEEEO EEE (Even, Odd) we go from left to right if E - just skip if O - if this first , we have to bring it to next O (because only two O's next each other can become EE) so we count distance to next O , than multiply by 2

that's our loaves to eliminate those two OO (so called price)and so on

if we ended up with still building chain (aka looking for next O) - means we have odd number of O's - no way to make them happy, print "NO"

`loaves = 0 isBuilding = False previousIndex = 0 for i in range(len(B)): if B[i] % 2 == 1: if isBuilding : loaves += (i - previousIndex) * 2 isBuilding = False else: isBuilding = True previousIndex = i return "NO" if isBuilding else loaves`

btmoulton + 1 comment start at

`B[0]`

and work through the array, up to`B[N-1]`

. if`B[i]`

is odd, then add one to`B[i]`

and add one to`B[i+1]`

. If the last number is odd, we won't be able to distribute bread evenly. If it is even, we have succeeded.int main(){ int N,breadAlloc; scanf("%d",&N); int *B = malloc(sizeof(int) * N); for(int B_i = 0; B_i < N; B_i++){ scanf("%d",&B[B_i]); } for(int i = 0; i < N-1; i++){ if(B[i]%2==1){ B[i]++; B[i+1]++; breadAlloc+=2; } } if(B[N-1]%2==1){ printf("NO"); } else{ printf("%d",breadAlloc); } return 0; }

barrun + 0 comments `B[i]++;`

on line 10 is unnecessary here; you only look forward and never use B[i] again.

amurdia + 1 comment I just bought the test case 20 and found that the expected output is 0. But as per the problem statement, if there is no solutions possible the output must be a string "NO". So the test case fails each time.

aregulivinayakAsked to answer + 1 comment In test case 20 every person in the line already has even number of loaves.You don't have to do anything,so the answer is 0.

amurdia + 0 comments Thanks a lot Vinayak, actually i figured that out after i posted the question coz others had got 25 points with the same set of testcases.

satyam_clay + 0 comments Return type is int.One can't return "NO",therefore make changes in main function as below:

**int result = fairRations(B); if(result==-1) bufferedWriter.write("NO"); else bufferedWriter.write(String.valueOf(result));**

Sort 273 Discussions, By:

Please Login in order to post a comment