lib.rs

pub struct Block {
    balance: u64,
}

fn get_balance(blocks: &Vec<Block>, index: usize) -> Option<u64> {
    // handle out of bounds
    match blocks.get(index) {
        Some(block) => Some(block.balance),
        None => None,
    }
}

pub fn find_balance_change(blocks: &Vec<Block>, start_index: usize, end_index: usize) -> usize {
    if start_index == end_index {
        return end_index;
    }
    // We know that there are at least 2 blocks to compare
    let mut found_index = start_index;
    let initial_balance = match get_balance(blocks, start_index) {
        Some(balance) => balance,
        None => return start_index, // This should never happen
    };

    for idx in start_index + 1..=end_index {
        let balance = get_balance(blocks, idx).expect("Has balance value");
        if initial_balance == balance {
            found_index = idx;
        } else {
            return found_index + 1;
        }
    }
    found_index
}

pub fn find_balance_change_v2(blocks: &Vec<Block>, start_index: usize, end_index: usize) -> usize {
    if start_index == end_index {
        return end_index;
    }
    // We know that there are at least 2 blocks to compare
    let initial_balance = match get_balance(blocks, start_index) {
        Some(balance) => balance,
        None => return start_index, // This should never happen
    };

    // binary search
    let mut mid = start_index + end_index / 2;
    let mut mid_balance = get_balance(blocks, mid).unwrap();
    let mut is_found = true;
    while mid_balance == initial_balance {
        let new_start_index = mid;
        mid = new_start_index + ((end_index - new_start_index) / 2);

        if new_start_index == mid {
            is_found = false;
            break;
        }
        mid_balance = get_balance(blocks, mid).unwrap();
    }
    if is_found {
        mid
    } else {
        start_index
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn case_test_find_balance_change_v2_found() {
        let blocks = vec![
            Block { balance: 123 },
            Block { balance: 123 },
            Block { balance: 123 },
            Block { balance: 133 },
            Block { balance: 133 },
        ];
        let result = find_balance_change_v2(&blocks, 0, 4);

        assert_eq!(3, result);
    }

    #[test]
    fn case_test_get_balance_on_empty_chain() {
        let blocks = vec![];
        let result = get_balance(&blocks, 0);
        assert_eq!(None, result);
    }

    #[test]
    fn case_test_get_balance_non_empty() {
        let blocks = vec![Block { balance: 1337 }];
        let result = get_balance(&blocks, 0);
        assert_eq!(Some(1337), result);
    }

    #[test]
    fn case_test_get_balance_index_out_of_bounds() {
        let blocks = vec![Block { balance: 1337 }];
        let result = get_balance(&blocks, 1);
        assert_eq!(None, result);
    }

    // find_balance_change_tests
    #[test]
    fn case_test_find_balance_change_not_found_empty() {
        let blocks = vec![];
        let result = find_balance_change(&blocks, 0, 0);

        assert_eq!(0, result);
    }

    #[test]
    fn case_test_find_balance_change_not_found() {
        let blocks = vec![Block { balance: 123 }];
        let result = find_balance_change(&blocks, 1, 1);

        assert_eq!(1, result);
    }

    #[test]
    fn case_test_find_balance_change_no_change() {
        let blocks = vec![
            Block { balance: 123 },
            Block { balance: 123 },
            Block { balance: 123 },
            Block { balance: 123 },
            Block { balance: 123 },
        ];
        let result = find_balance_change(&blocks, 0, 4);

        assert_eq!(4, result);
    }

    #[test]
    fn case_test_find_balance_change_balance_changed() {
        let blocks = vec![
            Block { balance: 123 },
            Block { balance: 123 },
            Block { balance: 123 },
            Block { balance: 133 },
            Block { balance: 133 },
        ];
        let result = find_balance_change(&blocks, 0, 4);

        assert_eq!(3, result);
    }
}