Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.9 kB
4
Indexable
package org.mmi.challenge;

import lombok.RequiredArgsConstructor;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {

    public static void main(String[] args) {
        int target = 99999;

        Pair root = new Pair(1, 1, 0);

        Queue<Pair> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Pair current = queue.remove();
            if (!current.hasGreater(target)) {
                if (current.contains(target)) {
                    System.out.println(current.distance);
                    break;
                }
                queue.add(current.leftChild());
                queue.add(current.rightChild());
            }
        }
    }


    @RequiredArgsConstructor
    static class Pair {
        private final int a;
        private final int b;
        private final int distance;


        public int hashCode() {
            return a + b;
        }

        public boolean equals(Object o) {
            return this.a == ((Pair) o).a && this.b == ((Pair) o).b;
        }

        public List<Pair> descendants() {
            return List.of(new Pair(a, a + b, distance + 1), new Pair(a + b, b, distance + 1));
        }

        public Pair leftChild() {
            return new Pair(a, a + b, distance + 1);
        }

        public Pair rightChild() {
            return new Pair(a + b, b, distance + 1);
        }

        public boolean contains(int target) {
            return a == target || b == target;
        }

        public boolean hasGreater(int target) {
            return a > target || b > target;
        }

        public int sum() {
            return a + b;
        }

        @Override
        public String toString() {
            return "(" + a + "," + b + ")";
        }
    }
}