HackerRank ‘Fair Rations’ Solution

Short Problem Definition:

You are the benevolent ruler of Rankhacker Castle, and today you’re distributing bread. Your subjects are in a line, and some of them already have some loaves. Times are hard and your castle’s food stocks are dwindling, so you must distribute as few loaves as possible according to the following rules:

  1. Every time you give a loaf of bread to some person i, you must also give a loaf of bread to the person immediately in front of or behind them in the line (i.e., persons i+1 or i-1).
  2. After all the bread is distributed, each person must have an even number of loaves.
Link

Fair Rations

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

The solution can be approached from either the beginning or the end of the array.

Let’s examine the following observation: The first and last person in the array can only receive a loaf if the person next to them also got one.

If there is only one person in the array, it can never receive a loaf of bread. If there are two people in the array, both need to receive a loaf. If there are three people in the array either 0, 2 or 3 people receive a loaf. If there are any loaves awarded, the middle person has to receive at least 1.

Iterate the array from the beginning and always give the loaf to any person that does not meet criteria #2. Since the last person can never receive a loaf alone, check that for the final YES/NO decision.

Solution:
#!/bin/python

import sys


N = int(raw_input().strip())
B = map(int,raw_input().strip().split(' '))

loafs = 0

for idx in xrange(N-1):
    if B[idx] % 2 == 0:
        continue
    B[idx] += 1
    B[idx+1] += 1
    loafs += 2

    
if B[-1] % 2 == 1:
    print "NO"
else:
    print loafs
# Rust
use std::io;

fn get_number() -> u32 {
    let mut line = String::new();
    io::stdin().read_line(&mut line).ok().expect("Failed to read line");
    line.trim().parse::<u32>().unwrap()
}

fn get_numbers() -> Vec<u32> {
    let mut line = String::new();
    io::stdin().read_line(&amp;mut line).ok().expect("Failed to read line");
    line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect()
}

fn main() {
    let n = get_number() as usize;
    let mut b = get_numbers();
    let mut loafs = 0;
    
    for idx in 0..(n-1) {
        if b[idx] % 2 == 0 {
            continue;
        }
        
        b[idx] += 1;
        b[idx+1] += 1;
        loafs += 2;
    }
    
    if b[n-1] % 2 == 1 {
        println!("{}", "NO");
    } else {
        println!("{}", loafs);
    }
    
}

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin