Знайдзіце найменшую двайковую лічбу, кратную дадзенаму ліку


Узровень складанасці серада
Часта пытаюцца ў амазонка Фуркайты LinkedIn Microsoft Snapdeal
Шырыня Першы пошук Графік

Пастаноўка праблемы

У задачы «Знайсці найменшы двайковы разрад, кратны дадзенаму ліку» гаворыцца, што вам даецца дзесятковы лік N. Такім чынам, знайдзіце найменшы кратны N, які змяшчае толькі двайковыя лічбы '0' і '1'.

Прыклад

37
111

Падрабязнае тлумачэнне можна знайсці ніжэй на ўбудаваным малюнку.

Падыход

Падыход заключаецца ў выкананні BFS абход з выкарыстаннем радка: '1' у якасці каранёвага вузла. Мы дадаем "0" і "1" да гэтага вузла і націскаем на радкі, атрыманыя ў выніку "10" і "11", у чаргу. Кожны раз, калі выскоквае радок з чаргі, мы дадаем "0" і "1" да выскакванай радка і адсоўваем выніковую радок назад у чаргу. Падчас абходу. Калі мы знаходзім радок, які цалкам падзяляе ўваходны нумар, мы проста вяртаем гэты радок.

  1. Памяншэнне складанасці: Мы памяншаем складанасць нашага падыходу, скарачаючы колькасць радкі апрацоўваецца падчас абходу BFS. Для кожнай апрацаванай радкі мы дадаем яе значэнне мода (астатак, калі апрацаваны радок дзеліцца на ўваходны нумар) на хэш-набор. Калі для пэўнай радка, гэта значэнне мода ўжо прысутнічае ў наборы. Затым мы не дадаем радок у чаргу абыходу BFS.
  2. прычына: Каб паменшыць складанасць, мы пазбягаем дадавання радкоў значэнне мода у чаргу. Гэта значыць, калі радок з пэўным значэннем мода ўжо прысутнічае ў чарзе альбо ўжо была апрацавана. Затым любы наступны радок з тым самым значэнне мода не дадаецца ў чаргу. Прычына гэтага: выкажам здагадку, што два радкі X і Y маюць аднолькавыя значэнні мода (астатняя частка, калі апрацаваная радок дзеліцца на ўваходны нумар), X меншая па значэнні, чым Y. Няхай Z - гэта яшчэ адна радок, якая пры даданні да Y дае нам лік, які дзеліцца на ўваходны нумар N. Калі так, то мы таксама можам дадаць гэты радок да X і ўсё роўна атрымаць лік, які дзеліцца на ўваходны нумар N. Такім чынам, мы можам бяспечна пазбягаць дадання Y у чаргу BFS.

Алгарытм

  1. Стварыць чаргу для BFS абход.
  2. Стварыць хэш-набор каб праверыць, ці сустракалася радок з пэўным значэннем мода.
  3. Пачніце развод BFS пасля націску зыходнай радкі "1" у чаргу.
  4. Падчас абходу:
    1. Выцягнуць радок з чаргі.
    2. Праверце, ці ёсць гэта модульнае значэнне
      1. калі модульнае значэнне роўна 0, то менавіта гэты радок - наш неабходны адказ.
      2. У адваротным выпадку праверце, ці ёсць модульнае значэнне ў наборы ці не.
  5. Калі гэтага модульнага значэння няма ў наборы хэшаў, дадайце "0" і "1" у выскакваную радок (розныя копіі).
  6. Дадайце гэтыя дзве радкі, атрыманыя пасля дадання "0" і "1" у чаргу для абыходу BFS.
  7. паўтараць крокі 4,5 і 6, пакуль не будзе знойдзены двайковы лік, кратны ўваходнаму дзесятковаму ліку.

Алгарытм намаляваны ніжэй:

Знайдзіце найменшую двайковую лічбу, кратную дадзенаму ліку

код

Код C ++, каб знайсці найменшую двайковую лічбу, кратную дадзенаму ліку

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

/* finds remainder when num is divided by N */
int mod(string num, int N)
{
    int value = 0;
    for(int i=0;i<num.length();i++)
    {
        value = 10*value + int(num[i] - '0');
        value %= N;
    }
    
    return value;
}

/* produces smallest binary digit multiple of given integer */
string smallestBinaryMultiple(int N)
{
    queue <string> q;
    unordered_set <int> us;
    
    string num = "1";
    q.push(num);
    
    /* BFS traversal */
    while(!q.empty())
    {
        string top = q.front(); q.pop();
        
        int modulus = mod(top,N);
        
        if(modulus == 0)
        return top;
        
        if(us.find(modulus) == us.end())
        {
            us.insert(modulus);
            q.push(top+"0");
            q.push(top+"1");
        }
    }
}

int main()
{
    int N = 37;
    cout<<smallestBinaryMultiple(N)<<endl;
    return 0;
}
111

Код Java, каб знайсці найменшую двайковую лічбу, кратную дадзенаму ліку

import java.util.*;
import java.io.*;

class TutorialCup 
{
    /* finds remainder when num is divided by N */
    static int mod(StringBuffer num, int N)
    {
        int value = 0;
        for(int i=0;i<num.length();i++)
        {
            value = 10*value + num.charAt(i) - '0';
            value %= N;
        }
        
        return value;
    }
    
    /* produces smallest binary digit multiple of given integer */
    static StringBuffer smallestBinaryMultiple(int N)
    {
        Queue <StringBuffer> q = new LinkedList<>();
        HashSet <Integer> us = new HashSet<Integer>();
        
        StringBuffer num = new StringBuffer("1");
        q.add(num);
        
        /* BFS traversal */
        while(!q.isEmpty())
        {
            StringBuffer top = q.poll();
            
            int modulus = mod(top,N);
            
            if(modulus == 0)
            return top;
            
            if(!us.contains(modulus))
            {
                us.add(modulus);
                
                StringBuffer appendZero = new StringBuffer(top);
                appendZero.append('0');
                
                StringBuffer appendOne = new StringBuffer(top);
                appendOne.append('1');
                
                q.add(appendZero);
                q.add(appendOne);
            }
        }
        
        return num;
    }

  public static void main (String[] args) 
  {
      int N = 37;
        System.out.println(smallestBinaryMultiple(N));
  }
}
111

Аналіз складанасці

Складанасць часу

T (n) = O (V + E), складанасць часу роўная колькасці элементаў, якія мы сустракаем да дасягнення неабходнага выніку.

Касмічная складанасць

A (n) = O (V), Складанасць прасторы таксама залежыць ад той жа метрыкі. Колькасць элементаў, з якімі мы сутыкаемся, перш чым прыйсці да патрэбнага выніку.

Такім чынам, цяжка зразумець, колькі вузлоў будзе прысутнічаць на графіцы, перш чым дасягнуць патрэбнага выніку.

V = колькасць вузлоў

E = рэбры на графіку