- Practice
- Algorithms
- Implementation
- Fair Rations
- Discussions

# Fair Rations

# Fair Rations

WatchandLearn + 27 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 + 3 comments Nice thinking!! Also B[i]+1 is unncessesary.. And boundaries check needed.. But really elegant logic..

baranoob + 0 comments I agree B[i] + 1 is unnecessary. But I do not agree that we need to boundary check for B[i] + 1 because if i is the last element then it cannot be odd.

Eros10 + 0 comments [deleted]kris_tobiasson + 0 comments Here is another compact JS approach:

let lastID = -1; let count = 0; for(let i = 0; i < B.length; i++){ if(B[i]%2 !== 0){ if(lastID === -1) { lastID = i; } else{ count += Math.abs(i - lastID)*2; lastID = -1; } } } return (lastID === -1) ? count : `NO`;

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 + 2 comments 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

jhabeeb602 + 1 comment I got confused. 7 is an odd number, right.but 7+7=14 which is an even number.

sharan_s + 0 comments Sum of two numbers (always):

`odd + odd = even odd + even = odd even + odd = odd even + even = even`

In your case:

`7 + 7 = 14 odd + odd = even`

So, if you count the number of odd loaves,

example: if the count was 5, then the count is odd

**odd count makes the Problem unsolvable.**

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 + 4 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]

mrDragonX + 0 comments but the input will be increasing order so no need to worry about 1 1 1

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 + 7 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 + 1 comment 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

rakshit_1698 + 0 comments thank you share your O(n) time complexity output

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.

anmoljain5995 + 0 comments Best among all, really a very nice approach.KUDOS

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 + 1 comment In other words:: If #of odd values is odd answer is going to be "No". No need to take sum.

eng_sidan + 0 comments how you return "No" while the function returns int value ?

kris_tobiasson + 0 comments Here's my JS approach:

let oddIDs = []; for(let i = 0; i < B.length; i++){ if(B[i]%2 !== 0){ oddIDs.push(i); } } if(oddIDs.length%2 !== 0) { return `NO`; } else{ let count = 0; for(let i = 0; i < oddIDs.length; i++){ count += Math.abs(oddIDs[i] - oddIDs[i+1]) * 2; i++; } return count; }

NiteshSharma5 + 0 comments I came up with a different approach in O(n) only no need to check for sum. here return 1 means NO.

// Complete the fairRations function below. int fairRations(vector<int> a) { int n=a.size(),r=0; for(int i=0;i<n-1;i++){ if(a[i]%2!=0){ a[i+1]++; r+=2; }} if(a[n-1]%2==0)return r; else{return 1;} }

sachinraj20195 + 1 comment **can any one tell me why this is wrong??**# here is my code in java

public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int arr[]=new int[n]; int sum=0; for(int i=0; i

`} if(sum%2==1) { System.out.println("NO"); } int count=0; for(int i=0; i<n; i++) { if(arr[i]%2!=0) { arr[i]=arr[i]+1; arr[i+1]=arr[i+1]+1; count+=2; } } System.out.println(count);`

}*

sachinraj20195 + 0 comments **i am highly confused my code is almost same then why it is giving array index out of bound exception in first case?? please help**

yatheeshyts10 + 0 comments you can make it more eficient by removing the statements:

for(int i = 0; i < N; i++) { if(B[i] % 2 != 0){ count+=1 } return count*2

Vishal_karki97 + 0 comments Or number(frequency) of odd numbers should be even

aurduino4967 + 0 comments sum of two odd numbers may be even so if the array may consist of two odds in that manner how could it obtain desired result

sataaa + 7 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 + 3 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!

qayum_khan_usa + 0 comments Here's similar

**Python3**code in modern HackerRank, where one defines a function.def fairRations(B): output = 0 ; M = len(B)-1 for i in range(M): if B[i]%2 : output += 2 ; B[i+1] += 1 return "NO" if B[M]%2 else output

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

karlajusten + 0 comments Hi! I came up with same solution. If someone is having a hard time to understand it, here's some examples to help:

First, notice that we need an even amount of odd numbers. Because the problem says that if we increase

*i*by one we need to increase*i+1*or*i-1*. So we need a even amount of odd numbers to get as result an array with only even numbers.**Example**:*B = 2 3 5 6*this array has two odd numbers. To make 3 became even we add 1 to it. Luckly, it has an neighbor with odd number. So we add to it too, like this*B = 2 4 6 6*. Now the array has only even number.But if there's even numbers between the the odd numbers? It will require more loaves.

**Example**:*B = 2 3 4 5 6*this array has two odd numbers. To make 3 became even we add 1 to and it's neighbor, like this*B = 2 4 5 5 6*. Now the odd number was pushed do the left, so we need to increse it and its neighbor too, like this*B = 2 4 6 6 6*. Finally the array has only even number.**Example**:*B = 2 3 4 4 4 5 6*this array has two odd numbers. To make 3 became even we add 1 to and it's neighbor, like this*B = 2 4 5 4 4 5 6*. Now the odd number was pushed do the left, so we need to increse it and its neighbor too, like this*B = 2 4 6 5 4 5 6*. If we continue with this process we will end up with*B = 2 4 6 6 6 6 6*Now notice that on the last two examples the amount of loaf increased by one 1 were it was odd and by two on the numbers between the odd ones. With that in mind, we can calculate the amout of loaves

amountLoaves = 1 + 2.evenNumbersBetweenOddOnes + 1;

And we repeat this for every two odd numbers in the original array;

**Example**:*B = 3 5 3 4 4 5*this array has four odd numbers on indexes 0, 1, 2, 5. So we calculate on indexes 0 and 1 which results in 2. And we calculate on indexes 2 and 5, which results in 1 + 2.2 + 1 = 6. And 2 + 6 = 8 is the result.Here's my code: https://www.hackerrank.com/challenges/fair-rations/submissions/code/130803395

ajsmith22 + 0 comments This is pretty much the same solution I came up with:

def fairRations(B): counting = False count = 0 for b in B: if counting: count += 2 if b % 2: counting = not counting else: if counting: return "NO" return count

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]

Sort 337 Discussions, By:

Please Login in order to post a comment