માન્ય બૂમરેંગ લીટકોડ સોલ્યુશન


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે Google
મઠ

સમસ્યા નિવેદન

આ સમસ્યામાં, અમને XY 2-D વિમાનમાં ત્રણ પોઇન્ટનો સમૂહ આપવામાં આવે છે. આપણે પાછા ફરવાની જરૂર છે કે શું તે બૂમરેંગ બનાવે છે કે નહીં, તે તે ત્રણ છે કે નહીં અલગ પોઇન્ટ અને કરવું નથી એક સીધી રેખા બનાવો.

ઉદાહરણ

Points = {{1 , 2} , {2 , 6} , {1 , 2}}
false
Points = {{1 , 1} , {2 , 3} , {6 , 7}}
true

પ્રથમ ઇનપુટમાં 3 માંથી બે સમાન બિંદુઓ છે, તેથી તે માન્ય બૂમરેંગ નથી અને અમે ખોટા છાપો. બીજા પરીક્ષણમાં 3 વિશિષ્ટ બિંદુઓ છે જે સીધી રેખાની રચના કરતા નથી અને આપણે સાચું છાપીએ છીએ.

માન્ય બૂમરેંગ લીટકોડ સોલ્યુશન

અભિગમ (opeાળ પરીક્ષણ)

સમસ્યામાં તપાસો કે જો તે સીધી રેખા છે, આપણે શીખ્યા છે કે ત્રણ જુદા જુદા પોઇન્ટ ફક્ત કોલિનિયર હોય છે જો દરેક જોડી પોઇન્ટ દ્વારા રચિત લાઇનનો opeાળ સમાન હોય. અહીં, આપણે તપાસવાની જરૂર છે:

  • જો પોઇન્ટ અલગ હોય
  • બિંદુઓ સીધી રેખા પર આવેલા નથી

જો પોઇન્ટ્સની કોઈપણ જોડી સમાન હોય, તો આપેલ ઇનપુટ કોલનેરીટી ટેસ્ટમાં પસાર થશે, કારણ કે કોઈપણ 2 પોઇન્ટ (અથવા એક જ બિંદુ) હંમેશા કોલિનિયર હોય છે. તેથી, આપણે ફક્ત slોળાવની સમાનતા માટે તપાસ કરવાની જરૂર છે. નોંધ લો કે જો કોઈપણ ત્રણ બિંદુઓ, પી 1, પી 2 અને પી 3 કોલિનિયર છે, તો અમારી પાસે છે

(y2 - y1): (x2 - x1) :: (y3 - y2): (x3 - x2), અથવા

(y2 - y1) * (x3 - x2) = (x2 - x1) * (y3 - y2)

જ્યાં એક્સ 1, એક્સ 2, એક્સ 3, વાય 1, વાય 2, વાય 3 એ પી 1, પી 2 અને પી 3 ના અનુરૂપ એક્સ અને ટી કોઓર્ડિનેટ્સ છે.

અલ્ગોરિધમ

  1. ડીએક્સ 1 પ્રારંભ કરો = નો તફાવત x- સંકલન પ્રથમ બે મુદ્દાઓ અને ડાય 1 = નો તફાવત વાય-સંકલન પ્રથમ બે મુદ્દાઓ
  2. એ જ રીતે, dx2 = નો તફાવત સ્ટોર કરો વાય-સંકલન છેલ્લા બે મુદ્દાઓ અને ડીવાય 2 = નો તફાવત વાય-સંકલન છેલ્લા બે મુદ્દા છે
  3. પરત જો ((dx1 * dy2)! = (Dx2 * dy1)) (slાળ પરીક્ષણ શરત)
  4. પરિણામ છાપો

માન્ય બૂમરેંગ લેટકોડ સોલ્યુશનનો અમલ

સી ++ પ્રોગ્રામ

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

bool isBoomerang(vector <vector <int> > &points)
{
    int dx1 = (points[1][0] - points[0][0]);
    int dy1 = (points[1][1] - points[0][1]);
    int dx2 = (points[2][0] - points[1][0]);
    int dy2 = (points[2][1] - points[1][1]);

    return (dx1 * dy2) != (dy1 * dx2);
}

int main()
{
    vector <vector <int> > points = {{1 , 1} , {2 , 3} , {6 , 7}};
    if(isBoomerang(points))
        cout << "true\n";
    else
        cout << "false\n";
    return 0;
}

જાવા પ્રોગ્રામ

class valid_boomerang
{
    public static void main(String args[])
    {
        int[][] points = {{1 , 1} , {2 , 3} , {6 , 7}};
        if(isBoomerang(points))
            System.out.println("true");
        else
            System.out.println("false");
    }

    static boolean isBoomerang(int[][] points)
    {
        int dx1 = (points[1][0] - points[0][0]);
        int dy1 = (points[1][1] - points[0][1]);
        int dx2 = (points[2][0] - points[1][0]);
        int dy2 = (points[2][1] - points[1][1]);

        return (dx1 * dy2) != (dy1 * dx2);
    }
}
true

માન્ય બૂમરેંગ લીટકોડ સોલ્યુશનનું જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (1) જેમ કે આપણે સતત સંખ્યાબંધ કામગીરી કરીએ છીએ.

જગ્યાની જટિલતા

ઓ (1) જેમકે આપણે સતત મેમરી જગ્યા વાપરીએ છીએ.